324. Wiggle Sort II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

You may assume the input array always has a valid answer.

Example 1:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.

Example 2:

Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]

Constraints:

• 1 <= nums.length <= 5 * 10^4
• 0 <= nums[i] <= 5000
• It is guaranteed that there will be an answer for the given input nums.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

Code

class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int[] temp = new int[nums.length];

        for(int i = 0; i < nums.length; i++){
            temp[i] = nums[i];
        }

        int mid = (nums.length - 1) / 2;
        int end = nums.length - 1;

        for(int i = 0; i < nums.length; i++){
            nums[i] = (i % 2 == 1) ? temp[end--] : temp[mid--];
        }
    }
}