Cyclic sort

Pattern: Cyclic Sort, Loop sort

The introduction comes from ：https://www.zhihu.com/question/36738189/answer/908664455 author ： Poor farmer

This model is about a method that has always been fun ： It can be used to deal with the problem that the values in the array are limited to a certain interval . This mode traverses the elements in the array one by one , If the current number is not where it should be , Let's exchange it with the number where it should be . You can try to put the number in its correct position , But the complexity will be O(n^2). In this case , It may not be the optimal solution . Therefore, the advantages of circular sorting are reflected .

How to identify this pattern ？

• These problems are generally designed to be sorted arrays , and The numerical value is generally satisfied in a certain interval
• If the question makes you need to be in order / In the flipped array , Look for the lost / Repetitive / The smallest element

summary : The key is to understand and apply Array values and Subscripts The relationship between .

Classic title ：

1、Cyclic Sort (easy)

​ Cyclic Sort

2、Find the Missing Number (easy)

268. Missing numbers

describe ：

​ Given an inclusion [0, n] in n Array of Numbers nums , find [0, n] The number that doesn't appear in the array in this range .

​ Advanced ：

​ Can you achieve linear time complexity 、 The algorithm only uses extra constant space to solve this problem ?

Example ：

Example 1：

 Input ：nums = [3,0,1]
 Output ：2
 explain ：n = 3, Because there is  3  A digital , So all the numbers are in range  [0,3]  Inside .2  It's the missing number , Because it didn't show up in  nums  in .

Example 2：

 Input ：nums = [0,1]
 Output ：2
 explain ：n = 2, Because there is  2  A digital , So all the numbers are in range  [0,2]  Inside .2  It's the missing number , Because it didn't show up in  nums  in .

Example 3：

 Input ：nums = [9,6,4,2,3,5,7,0,1]
 Output ：8
 explain ：n = 9, Because there is  9  A digital , So all the numbers are in range  [0,9]  Inside .8  It's the missing number , Because it didn't show up in  nums  in .

Example 4：

 Input ：nums = [0]
 Output ：1
 explain ：n = 1, Because there is  1  A digital , So all the numbers are in range  [0,1]  Inside .1  It's the missing number , Because it didn't show up in  nums  in .

Tips ：

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums  All the numbers in are   unique 

See the official answer ：https://leetcode-cn.com/problems/missing-number/solution/que-shi-shu-zi-by-leetcode/

Exclusive or operation ^( Two equal digits are 0, Unequal 1) Can be offset , for example

• 0^4=4

    0000 = 0
  ^ 0100 = 4 
  ------------
    0100 = 4			

• 4^4=0

    0100 = 4
  ^ 0100 = 4
  -----------
    0000 = 0

Set the initial value of the result to n, Then perform an XOR operation on each number in the array and its subscript , A number that is not offset is a missing number ：

class Solution {
    
    public int missingNumber(int[] nums) {
    
        if (nums.length == 0)
            return 0;
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
    
            res ^= nums[i];
            res ^= i;
        }
        return res;
    }
}

It can be used Gauss summation formula Find out [0…n][0…n] And , Subtract the sum of all the numbers in the array , You get the missing number . Gauss summation formula is

class Solution {
    
    public int missingNumber(int[] nums) {
    
        if (nums.length == 0)
            return 0;

        int sum = 0;
        for (int i = 1; i <= nums.length; i++) {
    
            sum += i;
            sum -= nums[i-1];
        }
        
        return sum;
    }
}

3、Find all Missing Numbers (easy)

448. Find all the missing numbers in the array

describe ：

​ Given a range in 1 ≤ a[i] ≤ n ( n = Array size ) Of integer array , Some elements in the array appear twice , Others only appear once .

​ Find all the [1, n] There are no numbers in the array between ranges .

​ You can use no extra space and the time complexity is O(n) Do you want to finish this task ? You can assume that the returned array is not included in the extra space .

Example :

 Input :
[4,3,2,7,8,2,3,1]

 Output :
[5,6]

Let's see the official solution , Is dubious

Finish the following step 4 After the title , Sudden understanding .

1 ≤ a[i] ≤ n. It can be downloaded from 0 To traverse the . Mark the subscript as nums[0...i]-1 Set the value of the array of to a negative number .

When you finish walking , The corresponding subscript of those numbers that do not appear is nums[i]-1 The value of must be positive .

In the example above nums[i] = 5 non-existent , So the subscript is nums[i] - 1 namely 5-1 = 4 That is to say nums[4] = 8 Must be positive , From this we can know the number of disappearances .

class Solution {
    
    public List<Integer> findDisappearedNumbers(int[] nums) {
    
        List<Integer> res = new ArrayList<>();      //  result 

        // 1 ≤ a[i] ≤ n,  Mark the subscript as  nums[i]-1  All numbers of are set to negative numbers 
        for (int i = 0; i < nums.length; i++) {
    
            int index = Math.abs(nums[i]) - 1;      //  Repeating numbers will  nums[i]  Set it to a negative number , So take the absolute value 
            if (nums[index] > 0)                    //  Greater than  0  All numbers of are set to negative numbers 
                nums[index] = -nums[index];
        }
        
        //  find   Positive subscript  + 1 Value , That is, the disappearing number 
        for (int i = 0; i < nums.length; i++) {
    
            if (nums[i] > 0)
                res.add(i + 1);
        }
        
        return res;
    }
}

4、Find the Duplicate Number (easy)

287. Look for repetitions

describe ：

​ Given an inclusion n + 1 Array of integers nums, The numbers are all in 1 To n Between （ Include 1 and n）, We know that there is at least one duplicate integer . Let's say there's only one repeating integer , Find out the number of repetitions .

Example ：

Example 1:

 Input : [1,3,4,2,2]
 Output : 2

Example 2:

 Input : [3,1,3,4,2]
 Output : 3

explain ：

​ You cannot change the original array （ Suppose the array is read-only ）.
​ Only use the extra O(1) Space .
​ Time complexity is less than O(n2) .
​ There is only one duplicate number in the array , But it may appear more than once .

Details available ： Double pointer

​ Create array subscript i And numbers nums[i] The mapping function of f(i).

​ Array [1,2,4,2,3] , Its mapping i -> f(i) by ：

0->1
1->2
2->4
3->2
4->3

From the subscript 0 set out , according to f(i) Work out a value , Take this value as the new subscript , Then calculate the function value , repeat . available ：

0->1->2->4->3->2->4->3->2->4.....

thus , You can use the previous theory . Speed pointer type No 2 topic ： Determine whether the linked list has a ring and return the ring entry point . That is, after finding the meeting point , Then use a pointer to go from the starting point to the slow pointer , They finally met at the entrance point of the ring .

class Solution {
    
    public int findDuplicate(int[] nums) {
    
        int slow = 0;       //  Slow pointer , Do a mapping 
        int fast = 0;       //  Quick pointer , Do mapping twice 

        //  There is at least one duplicate integer , So there must be a ring . Find the meeting point 
        do {
    
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while (slow != fast);

        //  Find the ring entry point .
        int head = 0;
        while (slow != head){
    
            head = nums[head];
            slow = nums[slow];
        }

        return head;
    }
}

5、Find all Duplicate Numbers (easy)

442. Duplicate data in array

describe ：

​ Given an array of integers a, among 1 ≤ a[i] ≤ n （n Is array length ）, Some of these elements appear twice and others once .

​ Find all elements that appear twice .

​ You don't have to go to any extra space and O(n) Do you solve this problem in time complexity ？

Example ：

 Input :
[4,3,2,7,8,2,3,1]

 Output :
[2,3]

By title 1 ≤ a[i] ≤ n , It can be downloaded from 0 To traverse the , Subscript one by one nums[0...i]-1 Set the value on to a negative number .

If there is a subscript nums[i]-1 The value of is already negative , Is repeated . namely num[i] = nums[i+n].

class Solution {
    
    public List<Integer> findDuplicates(int[] nums) {
    
        List<Integer> res = new ArrayList<>();  //  result 
        int index = 0;  //  Permutation array subscript : num[i] - 1
        for (int i = 0; i < nums.length; i++) {
    
            index = Math.abs(nums[i]) - 1;  //  Subscript of permutation 
            if (nums[index] < 0){
               //  The value of this subscript has been previously replaced , Is repeated 
                res.add(index + 1);         // index + 1  This is the number 
            }
            nums[index] = -nums[index];     //  Replace with a negative number 
        }

        return res;
    }
}