324. swinging sort II: not a simple construction problem

Title Description

This is a LeetCode Upper 「324. Swing sort II」 , The difficulty is 「 secondary 」.

Tag : 「 structure 」、「 Sort 」、「 Choose... Quickly 」

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 ：

• Topic data assurance , For a given input nums, Always produce results that meet the requirements of the topic

Advanced ： You can use   Time complexity and / Or in place Extra space to do it ？

structure （ Quick selection + Three number order ）

Even if this problem does not consider space Advanced requirements for , Only required In time , stay LC It is also a difficult problem . If it's the first time you've done , And hope that in a limited time （ No more than minute ） Make it inside , It can be said that it is even more difficult .

Essentially , The topic asks us to implement a construction method , To be able to nums Adjust to meet 「 swing 」 requirement .

Specific construction method ：

1. find nums The median , This step can be done by 「 Choose... Quickly 」 Algorithm to do , The time complexity is , The space complexity is , Suppose the median found is x;

2. according to And x The size of the relationship , take Divided into three categories （ Less than / be equal to / Greater than ）, Three types of operations can be divided into 「 Three number order 」 How to do it , The complexity is .

   When this is done , Our array is adjusted to ： , It's divided into 「 Less than x / be equal to x / Greater than x」 Three paragraph .

3. structure ： First put 「 Odd number 」 Subscript , Put again 「 even numbers 」 Subscript , The placement direction is 「 From left to right 」（ Subscripts can be placed from small to large ）, If the value placed is, then 「 From big to small 」.

   Before we get to this point , The upper bound of the space we use is , If there is no requirement for the upper bound of space , We can simply nums Copy , Then place according to the corresponding logic , But the final space complexity is （ The code is shown ）; If you don't want to affect the original upper bound of space , We need an extra pass 「 Looking for a regular / mathematics 」 The way , Find the mapping relationship between the original subscript and the target subscript （ function getIdx in ）.

It is easy to prove the correctness of the construction process （ That is to say, the tectonic process must be carried out smoothly ）： Because we are based on the value 「 From big to small 」 Place , If the constructed scheme is illegal , It must be that two adjacent values are equal （“ It should be increasing but actually decreasing ” perhaps “ It should be decreasing in real terms ” The situation has been 「 From big to small 」 Place rejected ）, And when the same value is placed in the adjacent position , That is, there is an odd subscript , And its adjacent even subscripts all have the same value , This is equivalent to that the number of occurrences of this value exceeds half of the total number , This is related to 「 The title itself guarantees that the data can be used to construct a swinging array 」 Conflicts .

Code ：

class Solution {
    int[] nums;
    int n;
    int qselect(int l, int r, int k) {
        if (l == r) return nums[l];
        int x = nums[l + r >> 1], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) swap(i, j);
        }
        int cnt = j - l + 1;
        if (k <= cnt) return qselect(l, j, k);
        else return qselect(j + 1, r, k - cnt);
    }
    void swap(int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
    int getIdx(int x) {
        return (2 * x + 1) % (n | 1);
    }
    public void wiggleSort(int[] _nums) {
        nums = _nums;
        n = nums.length;
        int x = qselect(0, n - 1, n + 1 >> 1);
        int l = 0, r = n - 1, loc = 0;
        while (loc <= r) {
            if (nums[getIdx(loc)] > x) swap(getIdx(loc++), getIdx(l++));
            else if (nums[getIdx(loc)] < x) swap(getIdx(loc), getIdx(r--));
            else loc++;
        }
    }
}

class Solution {
    int[] nums;
    int n;
    int qselect(int l, int r, int k) {
        if (l == r) return nums[l];
        int x = nums[l + r >> 1], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) swap(i, j);
        }
        int cnt = j - l + 1;
        if (k <= cnt) return qselect(l, j, k);
        else return qselect(j + 1, r, k - cnt);
    }
    void swap(int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
    public void wiggleSort(int[] _nums) {
        nums = _nums;
        n = nums.length;
        int x = qselect(0, n - 1, n + 1 >> 1);
        int l = 0, r = n - 1, loc = 0;
        while (loc <= r) {
            if (nums[loc] < x) swap(loc++, l++);
            else if (nums[loc] > x) swap(loc, r--);
            else loc++;
        }
        int[] clone = nums.clone();
        int idx = 1; loc = n - 1;
        while (idx < n) {
            nums[idx] = clone[loc--];
            idx += 2;
        }
        idx = 0;
        while (idx < n) {
            nums[idx] = clone[loc--];
            idx += 2;
        }
    }
}

• Time complexity ： The time complexity of quick selection is ; The sorting complexity of three numbers is . The overall complexity is
• Spatial complexity ： My habit is not to count the extra space consumption caused by recursion , But if it is a topic assignment In terms of space , Obviously, you can't follow your habits , The space complexity of quick selection is . The overall complexity is

Last

This is us. 「 Brush through LeetCode」 The first of the series No.324 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases