1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left += 1;
            right -= 1;
        }
        for (int i = 1; i < nums.length; i += 2) {
            swap(nums, i - 1, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

我最初的想法. 就是先sort然后两两配对. 如果是奇数个的话, 第0个元素自己一个是一对. 这样就满足奇数index大于等于偶数index. 但是奇数index要大于等于下一个pair的开头. 如果现在的状况是不一定满足的. 于是我们要把最右边的pair放到最左边, 第二右边放到第二左边, 此时最左边的pair的第1个元素一定大于等于它左边pair的第0个元素. 因为最左边的pair的第0个元素都大于等于左边pair的第0个元素. 于是就是先reverse sort好的array, 再两两reverse一下. 如果是奇数个元素, 最右边的元素是整个数组中最小的, 那它肯定也满足小于等于它左边的元素.

时间复杂度: O(nlogn)
空间复杂度: O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        for (int i = 2; i < nums.length; i += 2) {
            swap(nums, i - 1, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

我那个方法确实可以的, 这个更好一些. 如果有偶数个元素两两配对就可以, 如果是奇数个, 那么第0个元素自己一个人. 此时两两配对可能二者相等, 可能后者大于前者, 如果后者大于前者, swap一下, 此时前者大于等于后者, 但是此时的前者还大于等于上一个pair的后者吗? 是大于的, 因为现在的pair的两个元素都是大于之前所有元素的, 因此此时的交换不影响之前不等式的成立.

时间复杂度: O(nlogn)
空间复杂度: O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void wiggleSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if ((i % 2 == 0) == (nums[i - 1] < nums[i])) {
                swap(nums, i, i - 1);
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

这个方法最绝. 如果是奇数index的话, 自己的值一定要大于等于前一个数, 如果是偶数index(除了0), 自己的值要小于等于前一个值. 假设我们处在某个index i, i - 1及以前的数字都满足我们要求的关系. 此时假设i时奇数, 如果前一个数小于等于nums[i], 那么我们的关系是满足的, 我们就继续. 如果不是, 这就意味着前一个数大于nums[i], 交换过后, 此时的nums[i]大于前一个数, 满足我们的关系, 那么nums[i - 1]和nums[i - 2]的关系还满足吗? 满足的, 我们根据我们的假设之前的nums[i - 1]是 <= nums[i - 2]的, 我们交换过后, nums[i - 1]更小了, 于是nums[i - 1] <= nums[i - 2]是成立的. 对于i是偶数的时候, 我们用同样的逻辑依旧可以这样证明.

对于i是0, 我们无需操作, i是1, 我们这样操作, 如果进行了交换, 那么也不用担心因为index 0之前没有元素. 当i等于2的时候nums[i - 2]就有了实际的值了. 根据我们的逻辑, 我们操作就行.

总结一下就是如果i是奇数index, 并且前一个值大于我们, 和前一个值swap; 如果i是偶数index, 并且前一个值小于我们, 和前一个值swap. 于是就有了两种情况, 要么是i是奇数切前一个值大于我们或者i是偶数且前一个值小于我们. 于是这就有了我们if条件的那一行, ==两侧条件一样的时候(都为true或者都为false的时候), 我们需要swap. 这和find in rotated array那道题很像, 就是判断mid和target在那一侧array的时候.

这个真是天才.

时间复杂度: O(n)
空间复杂度: O(1)