leetcode_ 1470_ 2021.10.12

leetcode1470, Rearrange the array .

Law 1 ： The most obvious way to solve this problem is to open up an array again , Then copy the data of the old array to the new array according to its own index . Spatial complexity O(N).

class Solution {
    
public:
   vector<int> shuffle(vector<int>& nums, int n) {
    
       vector<int> v;
       v.resize(2 * n); // Open one 2n Array of sizes .
       for(int i = 0; i < 2 * n; i += 2){
    
           v[i] = nums[i/2];     
           v[i + 1] = nums[n + i/2];
       }
       return v;
   }
};

Although this method is easy to think of , But need O(N) Spatial complexity of . There are two next O(1) Time complexity method .

• Law two ：
  In the title nums[i] The maximum value does not exceed 1000, and 1000 It only needs 10 individual bits I can represent ,int Yes 32 A bit , We can make use of the rest 22 A bit ( Exactly 10 individual ) To store an ordered array . Then move all the data in the array to the right 10 individual bits that will do .

class Solution {
    
public:
    vector<int> shuffle(vector<int>& nums, int n) {
    
        for(int i = 0; i < 2 * n; i += 2){
    
            nums[i] |= (nums[i/2] & 0x3ff) << 10;
            nums[i + 1] |= nums[n + i/2] << 10;
        }
        for(int& e : nums){
    
            e >>= 10;
        }
        return nums;
    }
};

• The details here are nums[i/2] & -x3ff, because nums[i/2] Possible 10-19 The bit may have been changed , If you don't shield it, moving it to the left will cause problems .

• Law three ：

Use each nums[i] > 0 Conditions , We use negative numbers to mark . What are the marks ？ Mark nums[i] Whether it is in the sorted position . If so, it will nums[i] become - nums[i]; If not, then
adjustment nums[i];
Let's first calculate nums[i] It should be in the right place j, Then exchange nums[i] and nums[j]; here
nums[j] In the right place , We mark with negative numbers ; But at this time nums[i] Still may not be
The right place , At this point, however, we can take advantage of j(nums[i] Where I was originally ) Work out a new
nums[i] The right place , Then swap again , until nums[i] Is also replaced by a negative number . So cycle one
All over , Until all the numbers are in the right place .

class Solution {
    
public:
    vector<int> shuffle(vector<int>& nums, int n) {
    
       for(int i = 0; i < 2 * n; ++i){
    
           if(nums[i] > 0){
    
               int j = i; //j yes nums[i] retrieval ,j adopt i Work out ;

               while(nums[i] > 0){
    
               j = j < n ? 2 * j : (j - n) * 2 + 1; // Each cycle passes j Calculate the new index position 
                    swap(nums[i], nums[j]);
                    nums[j] = -nums[j]; //nums[j] Already in the right place , Mark as negative .
               }
           }  
       }
       for(auto& e : nums){
    
           e = -e;
       }
       return nums;
    }
};