leetcode_1470_2021.10.12

leetcode1470，重新排列数组。

法一：这道题目最明显的做法就是重新开辟一个数组，然后将旧数组的数据按照自己的索引拷贝到新数组中去。空间复杂度O(N)。

class Solution {
    
public:
   vector<int> shuffle(vector<int>& nums, int n) {
    
       vector<int> v;
       v.resize(2 * n); //开一个2n大小的数组.
       for(int i = 0; i < 2 * n; i += 2){
    
           v[i] = nums[i/2];     
           v[i + 1] = nums[n + i/2];
       }
       return v;
   }
};

这种方法虽然很容易想到，但是需要O(N)的空间复杂度。接下来有两种O(1)时间复杂度的方法。

• 法二：
  题目中说nums[i]最大值不超过1000，而1000只需要10个bits就可以表示，int有32个比特位，我们可以利用剩下的22个比特位(准确的说是10个)来存储排好序的数组。然后将数组中的所有数据右移10个bits即可。

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;
    }
};

• 这里的细节就是nums[i/2] & -x3ff,因为nums[i/2]可能的10-19位可能已经被改变了，如果不屏蔽掉直接左移就会出问题。

• 法三：

利用每个nums[i] > 0的条件，我们使用负数来标记。标记什么呢？标记nums[i]是否在排序后的位置上。如果在那么将nums[i]变成 - nums[i]; 如果不在那么就
调整nums[i]；
我们先计算出nums[i]应该在的位置j，然后交换nums[i]和nums[j]; 此时
nums[j]在正确的位置上，我们用负数标记; 但是此时nums[i]仍然可能不在
正确的位置，然而此时我们可以利用j(nums[i]本来处在的位置)计算出新的
nums[i]正确的位置，然后再次交换，直到nums[i]也被换成负数。这样循环一
遍，直到所有数字都在正确的位置。

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是nums[i]检索,j通过i算出;

               while(nums[i] > 0){
    
               j = j < n ? 2 * j : (j - n) * 2 + 1; //每次循环就通过j算出新的索引位置
                    swap(nums[i], nums[j]);
                    nums[j] = -nums[j]; //nums[j]已经在正确的位置上，标记为负数。
               }
           }  
       }
       for(auto& e : nums){
    
           e = -e;
       }
       return nums;
    }
};