[324. swing sequence II]

source ： Power button （LeetCode）

describe ：

Give you an array of integers nums, Rearrange it into nums[0] < nums[1] > nums[2] < nums[3]... The order of .

You can assume that all input arrays can get results that meet the requirements of the topic .

Example 1：

 Input ：nums = [1,5,1,1,6,4]
 Output ：[1,6,1,5,1,4]
 explain ：[1,4,1,5,1,6]  It is also the result that meets the requirements of the topic , It can be accepted by the problem determination program .

Example 2：

 Input ：nums = [1,3,2,2,3,1]
 Output ：[2,3,1,3,1,2]

Tips ：

• 1 <= nums.length <= 5 * 10⁴
• 0 <= nums[i] <= 5000
• Topic data assurance , For a given input nums , Always produce results that meet the requirements of the topic

Method 1 ： Sort

Ideas and algorithms

Code :

class Solution {
    
public:
    void wiggleSort(vector<int>& nums) {
    
        int n = nums.size();
        vector<int> arr = nums;
        sort(arr.begin(), arr.end());
        int x = (n + 1) / 2;
        for (int i = 0, j = x - 1, k = n - 1; i < n; i += 2, j--, k--) {
    
            nums[i] = arr[j];
            if (i + 1 < n) {
    
                nums[i + 1] = arr[k];
            }
        }
    }
};

Execution time ：8 ms, In all C++ Defeated in submission 99.09% Users of
Memory consumption ：17.3 MB, In all C++ Defeated in submission 35.37% Users of
Complexity analysis
Time complexity ： O(nlogn), among n Is the length of the array . The time complexity of array sorting is O(nlogn), The time complexity of traversing the array is O(n), The total time complexity is O(nlogn).
Spatial complexity ： O(n), among n Is the length of the array . You need to copy the original array once , The space needed is O(n).

Method 2 ： Three way syncopation

Ideas and algorithms

Code :

class Solution {
    
public:
    void wiggleSort(vector<int>& nums) {
    
        int n = nums.size();
        int x = (n + 1) / 2;
        int mid = x - 1;
        nth_element(nums.begin(), nums.begin() + mid, nums.end());
        for (int k = 0, i = 0, j = n - 1; k <= j; k++) {
    
            if (nums[k] > nums[mid]) {
    
                while (j > k && nums[j] > nums[mid]) {
    
                    j--;
                }
                swap(nums[k], nums[j--]);
            }
            if (nums[k] < nums[mid]) {
    
                swap(nums[k], nums[i++]);
            }
        }
        vector<int> arr = nums;
        for (int i = 0, j = x - 1, k = n - 1; i < n; i += 2, j--, k--) {
    
            nums[i] = arr[j];
            if (i + 1 < n) {
    
                nums[i + 1] = arr[k];
            }
        }
    }
};

Execution time ：16 ms, In all C++ Defeated in submission 75.61% Users of
Memory consumption ：17.1 MB, In all C++ Defeated in submission 78.20% Users of
Complexity analysis
Time complexity ： O(n), among n Is the length of the array . Found array sorted as k The time complexity required for the number of is O(n), The time complexity required for three-dimensional segmentation of an array is O(n), The time complexity of array placement is O(n), The total time complexity is O(n).
Spatial complexity ： O(n), among n Is the length of the array . You need to copy the original array once , The space needed is O(n).

Method 3 ： Index conversion

Ideas and algorithms

Code :

class Solution {
    
public:
    inline int transAddress(int i, int n) {
    
        return (2 * n - 2 * i - 1) % (n | 1);
    }

    void wiggleSort(vector<int>& nums) {
    
        int n = nums.size();
        int x = (n + 1) / 2;
        int mid = x - 1;
        nth_element(nums.begin(), nums.begin() + mid, nums.end());
        int target = nums[mid];
        for (int k = 0, i = 0, j = n - 1; k <= j; k++) {
    
            if (nums[transAddress(k, n)] > target) {
    
                while (j > k && nums[transAddress(j, n)] > target) {
    
                    j--;
                }
                swap(nums[transAddress(k, n)], nums[transAddress(j--, n)]);
            }
            if (nums[transAddress(k, n)] < target) {
    
                swap(nums[transAddress(k, n)], nums[transAddress(i++, n)]);
            }
        }
    }
};

Execution time ：8 ms, In all C++ Defeated in submission 99.09% Users of
Memory consumption ：16.8 MB, In all C++ Defeated in submission 90.93% Users of
Complexity analysis
Time complexity ： O(n), among n Is the length of the array . Found array sorted as k The time complexity required for the number of is O(n), The time complexity required for three-dimensional segmentation of an array is O(n), The total time complexity is O(n).
Spatial complexity ： O(logn). Find the first k Large elements require recursion , At this point, the space cost of recursion using stack space is expected to be O(logn).

Method four ： Recursive optimization

Ideas and algorithms

On the basis of method 3, we can sort the search array to the No k The function of large elements is optimized , Use non recursive implementation to find the k Big elements , Further optimize the space complexity .

Code ：

class Solution {
    
public:
    int partitionAroundPivot(int left, int right, int pivot, vector<int> &nums) {
    
        int pivotValue = nums[pivot];
        int newPivot = left;
        swap(nums[pivot], nums[right]);
        for (int i = left; i < right; ++i) {
    
            if (nums[i] > pivotValue) {
    
                swap(nums[i], nums[newPivot++]);
            }
        }
        swap(nums[right], nums[newPivot]);
        return newPivot;
    }

    int findKthLargest(vector<int> &nums, int k) {
    
        int left = 0, right = nums.size() - 1;
        default_random_engine gen((random_device())());
        while (left <= right) {
    
            uniform_int_distribution<int> dis(left, right);
            int pivot = dis(gen);
            int newPivot = partitionAroundPivot(left, right, pivot, nums);
            if (newPivot == k - 1) {
    
                return nums[newPivot];
            } else if (newPivot > k - 1) {
    
                right = newPivot - 1;
            } else {
     
                left = newPivot + 1;
            }
        }
        return nums[k - 1];
    }

    inline int transAddress(int i, int n) {
    
        return (2 * n - 2 * i - 1) % (n | 1);
    }

    void wiggleSort(vector<int>& nums) {
    
        int n = nums.size();
        int x = (n + 1) / 2;
        int mid = x - 1;
        int target = findKthLargest(nums, n - mid);
        for (int k = 0, i = 0, j = n - 1; k <= j; k++) {
    
            if (nums[transAddress(k, n)] > target) {
    
                while (j > k && nums[transAddress(j, n)] > target) {
    
                    j--;
                }
                swap(nums[transAddress(k, n)], nums[transAddress(j--, n)]);
            }
            if (nums[transAddress(k, n)] < target) {
    
                swap(nums[transAddress(k, n)], nums[transAddress(i++, n)]);
            }
        }
    }
};

Execution time ：168 ms, In all C++ Defeated in submission 11.66% Users of
Memory consumption ：16.9 MB, In all C++ Defeated in submission 86.81% Users of
Complexity analysis
Time complexity ： O(n), among n Is the length of the array . Found array sorted as k The time complexity required for the number of is O(n), The time complexity required for three-dimensional segmentation of an array is O(n), The total time complexity is O(n).
Spatial complexity ： O(1).