Skip to content

Latest commit

 

History

History
136 lines (100 loc) · 6.79 KB

README.md

File metadata and controls

136 lines (100 loc) · 6.79 KB
Raw

题目

参考

给出一个未排序的数组nums，对其进行排序使得nums[0] < nums[1] > nums[2] < nums[3] ...

例如，nums = [1,5,1,1,6,4]，一个可能的答案是 [1,4,1,5,1,6]

要求：

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

解答

先不管题目中对时间复杂度和空间复杂度的要求，看看这个问题有什么方法

假设数组已经按要求排好序，我们可以将元素分成两组：

  1. 奇数组（odd group）：包含所有下标为奇数的元素
  2. 偶数组（even group）：包含所有下标为偶数的元素

从“摆动序列”的性质可知，奇数组中的每个元素，都比排好序的数组中它的左右邻居大。只要能满足这个性质，就是一个正确的结果。但是，如果对于奇数组和偶数组只有着一条性质，那么想要解决这个问题还是无从下手。因此，可以对两个组添加一条性质：所有奇数组中的元素都大于等于偶数组中的元素， 。在添加这一条性质之后，我们依然可以通过转化使得前一条性质依然成立

证明：

假设有

奇数组 = [...,a,...]
偶数组 = [...,b,...]

并且 a < b

假设a的邻居为c和d，b的邻居为e和f，根据第一条性质有：

c < a 并且 d < a
b < e 并且 b < f

那么此时可以将a和b进行交换，交换后a变大为b，b变小为a，因此上述性质依然成立。经过大量这种交换后，最终奇数组中的任一元素都会大于等于偶数组中的所有元素。性质二描述了一种全局关系状态

有了性质二，就可以按下列2个步骤解决：

  1. Partition：将数组分成奇数组(L)和偶数组(S)，S拥有m（(n+1)/2）个元素，L拥有剩余的元素。并且两组中的元素符合性质二。L中的元素不会比S中的多
  2. Placement：将S中的元素放置到偶数下标，将L中的元素放置到奇数下标。但是S和L中可能包含重复元素，因此有可能放置后两个相邻元素相等从而产生错误。所以放置时需要一些技巧

首先，如果数组能够排成“摆动序列“，那么S和L中重复的元素不会超过S的大小，即m ： 假设重复的元素超过了m，当数组排成”摆动序列后“，因为它们相等，所以这些重复元素不能成为彼此的邻居，那么它们就必须占据所有偶数下标或者所有奇数下标。然而，即使这样也还是会有残余的元素没有位置，因为所有奇数下标的数量和所有偶数下标的数量都不会超过m

然后，如果将来自S中的重复元素放置在尽可能小的偶数下标，将来自L中的重复元素放置在尽可能大的奇数下标，那么重复元素就不会出现相邻的情况。假设这个重复元素在S中的总数为k1，在L中的总数为k2，k = k1 + k2为重复元素的总数

  • 如果数组大小n为偶数：
    • 那么k <= m = n/2。在放置后，那么S中该重复元素最后一个的下标为2 * (k1 - 1)，L中该重复元素最后一个的下标为(n - 1) - 2 * (k2 - 1)。如果前一个下标比后一个下标至少小1，那么重复元素就不会相邻。这是成立的：2 * (k1 - 1) + 1 < (n - 1) - 2 * (k2 - 1) <==> k1 + k2 < [n/2] + 1 and k1 + k2 = k <= n/2 = [n/2] < [n/2] + 1
  • 如果数组大小n为奇数：
    • 如果k = (n + 1)/2，只有当k2 = 0时，才能排序成”摆动序列“。例如，所有S中重复元素占据所有偶数下标。
    • 否则有k1 + k2 = k < (n + 1)/2 = [n/2] + 1 无论哪种情况下，这样的放置策略都会分散重复元素，使得它们不会相邻

一旦所有重复元素按上面的策略放置后，将所有S和L中的其余元素分别放置到剩余偶数下标和剩余奇数下标，最终得到了一个”摆动序列“

1）方法一：O(nlogn)时间 O(n)空间

排序，将元素分为上述L和S两组。用j表示映射后的坐标，j和i的关系如下：

// i = [0,1,2,3,...]
// j = [1,3,5,...,0,2,4,...]
j = (2 * i + 1) % (n | 1)

因为放置时可能占用了未遍历到的位置，所以使用一个预留数组，在进行遍历处理之前保存元素

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        //m为偶数下标的个数
        int n = nums.size(), m = (n + 1) >> 1;
        vector<int> copy = nums;
        sort(copy.begin(),copy.end());

        //处理偶数组
        //i: [m-1,...,0]（数组的前半部分，即偶数组的元素，共m个），先遍历到的是中间元素
        //j: [0,2,4...]（放置的下标，从左往右放置，中间元素在左边）
        for (int i = m - 1, j = 0; i >= 0; i--, j += 2) nums[j] = copy[i];
        //处理奇数组
        //i: [n-1,...,m]（数组的后半部分，即奇数组的元素），先遍历到的不是中间元素
        //j: [1,3,5...]（放置的下标，从左往右放置，中间元素在右边）
        for (int i = n - 1, j = 1; i >= m; i--, j += 2) nums[j] = copy[i];
    }
};

2）方法二：O(n)时间 O(n)空间

由于只需要将元素划分成S和L，因此没必要对数组进行排序，使用基于partition的方法找到中值，将数组分为S和L两部分，可以将排序的时间复杂度从O(nlogn)降到O(n)，从而整个时间复杂度变成O(n)

3）方法三：O(n)时间 O(1)空间

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        //m为偶数下标的个数
        int n = nums.size(), m = (n + 1) >> 1;
        //lambda，将下标i进行映射
        auto mapping=[n](int i)->int{return (1 + 2 * i) % (n | 1);};
        //获取中值
        auto miditr = nums.begin() + m - 1;
        nth_element(nums.begin(), miditr , nums.end());
        int median = *miditr;
    
        //j:          [0,1,2,3,...] （j > k时终止）
        //mapping[j]: [1,3,5,...,0,2,4,...]
        //
        //i:          [0,1,2,3,...]
        //mapping[i]: [1,3,5,...,0,2,4,...]
        //k:          [n-1,n-2,...]
        //mapping[k]: [...,4,2,0,...,5,3,1]
        for (int i = 0, j = 0, k = n - 1; j <= k;) {
            if (nums[mapping(j)] > median) //找到一个比中值大的数
                swap(nums[mapping(i++)], nums[mapping(j++)]);
            else if(nums[mapping(j)] < median)  //找到一个比中值小的数，这里j不变
                swap(nums[mapping(j)], nums[mapping(k--)]);
            else   //找到一个和中值相等的元素
                j++;
        }
    }
};

参考