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].

To give an array without sorting, reorder it to nums [0] & lt; = nums [1] &> = nums [2] & lt; = nums [3].

Solution: traverse the array, if it is an odd position and its value is larger than the next, then exchange its value, if it is an even position and its value is smaller than the next, then exchange its value. The time complexity is O (n). Note that the difference between the index and the actual position is 1, so the parity is opposite.

Java:

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length < 2) return;
        for (int i = 1; i < nums.length; i++) {
            if ((i % 2 == 0 && nums[i] &> nums[i - 1]) || (i % 2 == 1 && nums[i] < nums[i - 1])) {
                int tmp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = tmp;
            } 
        }
    }
}　　

Java:

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

Python:

# Time:  O(n)
# Space: O(1)
class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        for i in xrange(1, len(nums)):
            if ((i % 2) and nums[i - 1] &> nums[i]) or \
                (not (i % 2) and nums[i - 1] < nums[i]):
                # Swap unordered elements.
                nums[i - 1], nums[i] = nums[i], nums[i - 1]

C++:

// Time:  O(n)
// Space: O(1)
class Solution {
public:
    void wiggleSort(vector<int&>& nums) {
        for (int i = 1; i < nums.size(); ++i) {
            if (((i % 2) && nums[i] < nums[i - 1]) ||
                (!(i % 2) && nums[i] &> nums[i - 1])) {
                // Swap unordered elements.
                swap(nums[i], nums[i - 1]);
            }
        }
    }
};　

C++:

// Time Complexity O(nlgn)
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]);
        }
    }
};

C++:

// Time Complexity O(n)
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] < nums[i - 1]) || (i % 2 == 0 && nums[i] &> nums[i - 1])) {
                swap(nums[i], nums[i - 1]);
            }
        }
    }
};

>>

Similar theme:

[LeetCode] Wiggle Sort II free action II

All LeetCode Questions List Total