Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
The obvious solution is to just sort the array first, then swap elements pair-wise starting from the second element. For example:
\n[1, 2, 3, 4, 5, 6]\n \xe2\x86\x91 \xe2\x86\x91 \xe2\x86\x91 \xe2\x86\x91\n swap swap\n\n=> [1, 3, 2, 5, 4, 6]\n
public void wiggleSort(int[] nums) {\n Arrays.sort(nums);\n for (int i = 1; i < nums.length - 1; i += 2) {\n swap(nums, i, i + 1);\n }\n}\n\nprivate void swap(int[] nums, int i, int j) {\n int temp = nums[i];\n nums[i] = nums[j];\n nums[j] = temp;\n}\n
Complexity analysis
\nTime complexity : .\nThe entire algorithm is dominated by the sorting step, which costs time to sort elements.
\nSpace complexity : . Space depends on the sorting implementation which, usually, costs auxiliary space if heapsort is used.
Intuitively, we should be able to reorder it in one-pass. As we iterate through the array, we compare the current element to its next element and if the order is incorrect, we swap them.
\npublic void wiggleSort(int[] nums) {\n boolean less = true;\n for (int i = 0; i < nums.length - 1; i++) {\n if (less) {\n if (nums[i] > nums[i + 1]) {\n swap(nums, i, i + 1);\n }\n } else {\n if (nums[i] < nums[i + 1]) {\n swap(nums, i, i + 1);\n }\n }\n less = !less;\n }\n}\n
We could shorten the code further by compacting the condition to a single line. Also observe the boolean value of less actually depends on whether the index is even or odd.
public void wiggleSort(int[] nums) {\n for (int i = 0; i < nums.length - 1; i++) {\n if (((i % 2 == 0) && nums[i] > nums[i + 1])\n || ((i % 2 == 1) && nums[i] < nums[i + 1])) {\n swap(nums, i, i + 1);\n }\n }\n}\n
Here is another amazing solution by @StefanPochmann who came up with originally here.
\npublic void wiggleSort(int[] nums) {\n for (int i = 0; i < nums.length - 1; i++) {\n if ((i % 2 == 0) == (nums[i] > nums[i + 1])) {\n swap(nums, i, i + 1);\n }\n }\n}\n
Complexity analysis
\nTime complexity : .\nIn the worst case we swap at most times. An example input is [2,1,3,1,4,1].
Space complexity : .
\n