LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 将中位数放到中间，左侧放更小的元素，右侧放更大的元素，接着把右侧元素依次插入到左侧即可
• 题目要求 O(1) 空间，不能使用额外数组。用宏给数组定义一个映射，映射数组的左侧对应奇数位置的数，这样只要映射数组的左侧都是比右侧大的数，则原数组就会变成摆动排序

a(0) = nums[1]
a(1) = nums[3]
a(2) = nums[5]
a(3) = nums[0]
a(4) = nums[2]
a(5) = nums[4]

nums = 111465
a(i) = 145116
i    = 012345

目标情况：
nums = 161514
a(i) = 654111
i    = 012345

• 实现如下

class Solution {
 public:
  void wiggleSort(vector<int>& nums) {
    if (empty(nums)) {
      return;
    }
    int sz = size(nums);
    nth_element(begin(nums), begin(nums) + sz / 2, end(nums));
    int m = nums[sz / 2];
#define a(i) nums[(2 * (i) + 1) % (sz | 1)]
    int i = 0;
    int j = 0;
    int k = sz - 1;
    while (j <= k) {
      if (a(j) > m) {
        swap(a(i), a(j));
        ++i;
        ++j;
      } else if (a(j) < m) {
        swap(a(j), a(k));
        --k;
      } else {
        ++j;
      }
    }
  }
};