关于程序员:324-摆动排序-II-不简单的构造题

题目形容

这是 LeetCode 上的 324. 摆动排序 II，难度为 中等 。

Tag :「结构」、「排序」、「疾速抉择」

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的程序。

你能够假如所有输出数组都能够失去满足题目要求的后果。

示例 1：

 输出：nums = [1,5,1,1,6,4]

输入：[1,6,1,5,1,4]

解释：[1,4,1,5,1,6] 同样是合乎题目要求的后果，能够被判题程序承受。

示例 2：

 输出：nums = [1,3,2,2,3,1]

输入：[2,3,1,3,1,2]

提醒：

• $1 <= nums.length <= 5 \times 10^4$
• $0 <= nums[i] <= 5000$
• 题目数据保障，对于给定的输出 nums，总能产生满足题目要求的后果

进阶：你能用 $O(n)$ 工夫复杂度和 / 或原地 $O(1)$ 额定空间来实现吗？

结构（快选 + 三数排序）

这道题即便不思考空间 $O(1)$ 的进阶要求，只要求做到 $O(n)$ 工夫的话，在 LC 上也属于难题了。如果大家是第一次做，并且心愿在无限工夫（不超过 $20$ 分钟）内做进去，能够说是难上加难。

实质上，题目要咱们实现一种构造方法，可能将 nums 调整为满足「摆动」要求。

具体的构造方法：

1. 找到 nums 的中位数，这一步能够通过「疾速抉择」算法来做，工夫复杂度为 $O(n)$，空间复杂度为 $O(\log{n})$，假如找到的中位数为 x；

2. 依据 $nums[i]$ 与 x 的大小关系，将 $nums[i]$ 分为三类（小于 / 等于 / 大于），划分三类的操作能够采纳「三数排序」的做法，复杂度为 $O(n)$。

   这一步做完之后，咱们的数组调整为：$[a_1, a_2, a_3, … , b_1, b_2, b_3, … , c_1, c_2, c_3]$，即分成「小于 x / 等于 x / 大于 x」三段。

3. 结构：先放「奇数」下标，再放「偶数」下标，搁置方向都是「从左到右」（即可下标从小到大进行搁置），搁置的值是则是「从大到小」。

   到这一步之前，咱们应用到的空间上界是 $O(\log{n})$，如果对空间上界没有要求的话，咱们能够简略对 nums 进行拷贝，而后依照对应逻辑进行搁置即可，但这样最终的空间复杂度为 $O(n)$（代码见 $P2$）；如果不心愿影响到原有的空间上界，咱们须要额定通过「找法则 / 数学」的形式，找到原下标和指标下标的映射关系（函数 getIdx 中）。

容易证实该结构过程的正确性（即该结构过程必然能顺利进行）：因为咱们是依照值「从大到小」进行搁置，如果结构进去的计划不非法，必然是相邻的两个值为相等（“该当递增理论递加”或者“该当递加理论递增”的状况已被「从大到小」进行搁置所否决），而当相邻地位搁置了雷同的值，即存在某个奇数下标，以及其相邻的偶数下标都搁置了雷同的值，这等价于该值呈现次数超过总个数的一半，这与「题目自身保证数据可能结构出摆动数组」所抵触。

代码：

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

• 工夫复杂度：快选的工夫复杂度为 $O(n)$；三数排序复杂度为 $O(n)$。整体复杂度为 $O(n)$
• 空间复杂度：我的习惯是不算递归带来的额定空间耗费的，但如果是题目指定 $O(1)$ 空间的话，显然是不能依照习惯来，快选的空间复杂度为 $O(\log{n})$。整体复杂度为 $O(\log{n})$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.324 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布