preface

Joseph ring problem is quite a classic problem in the algorithm, its problem understanding is quite easy, and the problem description has a lot of versions, and Joseph ring problem there are a lot of deformation, this Explanation of Joseph problem, can certainly take you to understand all!

What is the Joseph ring problem?

The Joseph ring problem is “optimized” to describe differently on different platforms, such as the game called “kids” in the offer of the cow sword, and the game called “kill”, “roll call”… The most immediate feeling is the one at offer62’s description: the last remaining number in the circle.

Problem Description:

0,1,···,n-1 The n numbers are arranged in a circle, starting with the number 0, and each time the MTH number is removed from the circle. Find the last number left in the circle.

For example, the digits 0, 1, 2, 3, and 4 form a circle. If you delete the third digit starting from 0, the first four digits will be 2, 0, 4, and 1, so the last remaining digit will be 3.

Of course, I’m going to consider m and n as normal data ranges, where

  • 1 <= n <= 10^5
  • 1 <= m <= 10^6

You may have an image of a group of village children sitting together as a child, counting from one line to the next, and then starting again until the last.

Cyclic linked list simulation

The essence of this problem is the problem of circular linked lists, surrounded by a circle, there is no end this is a typical circular linked list! A sequential enumeration, that is not the list traversal enumeration! Count to the corresponding number out of the column, this is not the circular list deletion!

And there are also very convenient places:

  • The downward enumeration of the circular list does not need to worry about the head and tail. Node =node.next downward enumeration
  • Next = node.next-next; next= node.next-next

Of course, there are some caveats

  • Circular lists are easy to form by pointing next from the last node of a regular list to the first node

  • Stop returning when there is only one node in the loop, i.e. node.next=node

  • Delete, we need to find the previous node to delete, so we need to delete the count of one bit less, use the previous node directly delete the next node can be

In this way, the idea is clear and the code is opened directly:

class Solution {
    class node// List nodes{
        int val;
        public node(int value) {
            this.val=value;
        }
        node next;
    }
    public int lastRemaining(int n, int m) {
        if(m==1)return n-1;// Return the last one one at a time
        node head=new node(0);
        node team=head;// Create a linked list
        for(int i=1; i<n; i++) { team.next=new node(i);
            team=team.next;
        }
        team.next=head;// make a ring
        int index=0;// Count from 0
        while(head.next! =head) {// When more than one node is left
            // If index=m-2 then the next node (m-1) should be deleted
            if(index==m-2)
            {
                head.next=head.next.next;
                index=0;
            }
            else {
                index++;
            }
            head=head.next;
        }
        returnhead.val; }}Copy the code

Of course, this algorithm is too complex, you cannot submit most OJ AC, because the timeout is too serious, we can analyze the details below.

Ordered set simulation

Using a linked list to simulate the game directly above would result in a very, very serious timeout, n digits, counting to the MTH column. Because if M is very large and much larger than m, then you’re going to go around a lot.

So we can use the method of complementation to determine the lowest number of equivalent enumerations, and then delete it. Here you can continue to use the self-built list to simulate the while loop above and add only one record length of each complementation loop above:

int len=n;
while(head.next! =head) {if(index==(m-2)%len)
  {
    head.next=head.next.next;
    index=0;
    len--;
  }
  else {
    index++;
  }
  head=head.next;
}
Copy the code

But a lot of times we don’t write a LinkedList simulation by hand, we do it with ArrayList and LinkedList, and if we use LinkedList the underlying data structure is also a LinkedList, if we use ArrayList the underlying data structure is an array. But the code is the same when using List.

List can know the length directly, also can delete the element, the difficulty of using List is how to simulate a sequential List as a circular List?

Let’s think carefully: if the current length is n and the number reaches the MTH, delete it at the index position. So what’s left after the deletion is the n-1 length, and the index position is the position of the first count, and we can tell how many steps it takes to get to the next deletion by taking the remainder, so what’s the next position?

You can sort it out to see if the number of walks is out of bounds, but there’s a more subtle way to find the exact location of the next walk, and the formula is:

index=(index+m-1)%(list.size());
Copy the code

Because index is one, if it’s a loop then m minus one is the real length, but we can assume that we’re going to multiply the length of this ordered set by several times, and then we’re going to start with index and find the position that we’re assuming is not cyclic, index2, and finally we’re going to take that position index2%, which is the real length.

Using this formula can not only solve the problem of m being too large and too many cycles above, but also find the real position. That is to assume that the ring is linear first and then find the real position. If you don’t understand, you can look at this figure again:

In this case, most OJ can barely pass, and the probability of the interviewer level is similar. The specific code is:

class Solution {
    public int lastRemaining(int n, int m) {
        if(m==1)
            return n-1;
        List<Integer>list=new ArrayList<>();
        for(int i=0; i<n; i++) { list.add(i); }int index=0;
        while (list.size()>1)
        {
            index=(index+m-1)%(list.size());
            list.remove(index);
        }
        return list.get(0); }}Copy the code

Recursively

Let’s review the optimization procedure above, which can solve the case where M is much, much larger than n (i.e. theoretically requires many, many revolutions) by taking the remainder. However, there may also be a case where N itself is very large, and it is inefficient to frequently query and delete both the ordered ArrayList and the LinkedList.

So smart people start looking for patterns or relationships in the data.

Throw the formula first:

F (n,m)=(f(n-1,m)+m)%n f(n,m) refers to n individuals, indicating the MTH number and the final number of the columnCopy the code

Here’s a closer look at my analysis process:

So let’s say we have 0, 1, 2,3, 4, 5, 6, 7, 8, 9 numbers, and let’s say m is 3, we can call it f of 10,3, even though we don’t know what it is.

When I do it for the first time, I find element 2 and delete it, and there are nine elements left, but the starting position is element 3. This is equal to 3, 4, 5, 6, 7, 8, 9, 0, 1.

At this point, the final remaining value of this sequence is f(10,3). The value of this sequence is different from f(9,3), but they are all 9 numbers and m is equal to 3. Therefore, the deletion position is the same. So what we need to do is see if there’s any connection between this sequence and f of 9 and 3.

The first two things to remember in this search are that the **% symbol ** can be used to augment the numbers effectively, i.e. we can treat the sequence 3,4,5,6,7,8,9,10,11 as (3,4,5,6,7, 9,10,11)%10. This 10 is the value of n.

In addition, if the values are continuous, then the final result can be found (the difference is a custom). So we can find the relationship between the results of f(10,3) and f(9,3), as shown in the following figure:

Therefore, the result of f(10,3) can be translated into the expression of f(9,3), and the following is the same:

(10, 3) = f (f (9, 3) + 3) % 10 (9, 3) = f (f (8, 3) + 3) % 9... F (2, 3) = (f (1, 3) + 3) % 2 f (1, 3) = 0Copy the code

In this way, we can find recursive relationships directly from numerical relationships without having to simulate them, and we can easily write code:

class Solution {
    int index=0;
    public int lastRemaining(int n, int m) {
         if(n==1)
            return 0;      
        return (lastRemaining(n-1,m)+m)%n; }}Copy the code

However, recursive efficiency is worse than direct iteration because there is a round-trip procedure. It can also iterate backwards and forwards:

class Solution {
    public int lastRemaining(int n, int m) {
        int value=0;
            for(int i=1; i<=n; i++) { value=(value+m)%i; }returnvalue; }}Copy the code

conclusion

Through this article, I think you should grasp and understand the problem of Joseph ring, the probability of the naked Joseph ring problem is very big, very frequent, chain table simulation is fundamental ideas, ordered set simulation list is promoted, and the recursive formula is the most worth learning place, if you don’t understand at first contact can re-read it. If you can use the formula to recurse to the interviewer to say a few words, explain the principle, that will make the interviewer’s eyes shine!

Original public account: Bigsai

If you feel that there is a harvest of this article welcome to like, collect, share a wave, also welcome to pay attention to my public number (Bigsai), add my V letter friends (Q1315426911) to learn and exchange, I also created a force buckle card group, where many enthusiastic partners hope to progress together!