leetcode刷题39——摆动排序系列

1.摆动排序

数组摆动排序：就地排序数组，不需要额外数组，满足以下性质：nums[0]<=nums[1]>=nums[2]<=nums[3]…

思路1：先给数组排个序，然后只要每次把第三个数和第二个数调换个位置，第五个数和第四个数调换个位置，以此类推直至数组末尾。

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        if (nums.size() <= 2) return;
        for (int i = 2; i < nums.size(); i += 2) 
            swap(nums[i], nums[i - 1]);
    }
};
           

思路2：根据题目要求的 nums[0] <= nums[1] >= nums[2] <= nums[3]…，可以总结出如下规律：

当i为奇数时，nums[i - 1] <= nums[i]；当i为偶数时，nums[i - 1] >= nums[i]。

那么只要对每个数字，根据其奇偶性，跟其对应的条件比较，如果不符合就和前面的数交换位置即可。

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        if (nums.size() <= 1) return;
        for (int i = 1; i < nums.size(); ++i) 
            if ((i % 2 == 1 && nums[i-1] > nums[i]) || (i % 2 == 0 && nums[i-1] < nums[i])) 
                swap(nums[i-1], nums[i]);
    }
};
           

2.摆动排序 II

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

你可以假设所有输入数组都可以得到满足题目要求的结果。

思路1：先对数组排序，分为大数部分和小数部分，再穿插排序。

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> tmp=nums;
        sort(tmp.begin(),tmp.end());
        reverse(tmp.begin(),tmp.end());
        int j=tmp.size()/2,k=0;
        for(int i=0;i<nums.size();++i)
        {
            if(i%2==0)  nums[i]=tmp[j++];
            else    nums[i]=tmp[k++];
        }
    }
};
           

思路2：三向切分

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        std::nth_element(nums.begin(), nums.begin() + n/2, nums.end());
        int mid = nums[n/2];
        
        // 3-way-partion
        int i = 0;
        int j = 0;
        int k = n - 1;

        #define a(i) nums[(2*(i)+1)%(n|1)]
        
        while (j <= k) 
        {
            if (a(j) > mid)
            {
                swap(a(i), a(j));
                ++i;
                ++j;
            }
            else if (a(j) < mid) 
            {
                swap(a(j), a(k));
                --k;
            }
            else 
                ++j;
        }
    }
};
           

3.摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

考察知识点：动态规划

解题思路：假设 up[i] 表示 nums[0:i] 中最后两个数字递增的最长摆动序列长度，down[i] 表示 nums[0:i] 中最后两个数字递减的最长摆动序列长度，只有一个数字时默认为 1。接下来我们进行分类讨论：

（1）nums[i+1] > nums[i]

假设 down[i] 表示的最长摆动序列的最远末尾元素下标正好为 i，遇到新的上升元素后，up[i+1] = down[i] + 1 ，这是因为 up 一定从 down 中产生（初始除外），并且 down[i] 此时最大。

假设 down[i] 表示的最长摆动序列的最远末尾元素下标小于 i，设为 j，那么 nums[j:i] 一定是递增的，因为若完全递减，最远元素下标等于 i，若波动，那么 down[i] > down[j]。由于 nums[j:i] 递增，down[j:i] 一直等于 down[j] ，依然满足 up[i+1] = down[i] + 1 。

（2）nums[i+1] < nums[i]，类似第一种情况。

（3）nums[i+1] == nums[i]，新的元素不能用于任何序列，保持不变。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size()<2)  return nums.size();
        int up=1,down=1;
        for(int i=1;i<nums.size();++i)
        {
            if(nums[i-1]<nums[i])   up=down+1;
            if(nums[i-1]>nums[i])   down=up+1;
        }
        return max(up,down);
    }
};