Wiggle Sort II

Question:
http://www.lintcode.com/en/problem/wiggle-sort-ii/
Given an unsorted array nums, reorder it such that
nums[0] < nums[1] > nums[2] < nums[3]....

Answer:

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: nothing
     */
    inline int partion(vector<int> &nums, int left, int right) {
        int pivot = nums[left];
        int i = left - 1;
        int j = right + 1;
        while (1) {
            do {
                i = i + 1;
            } while (nums[i] < pivot);
            do {
                j = j -1;
            } while (nums[j] > pivot);
            if (i >= j)
                return j;
            int temp = nums[i];            
            nums[i] = nums[j];            
            nums[j] = temp;             
        }
    }
    inline void qsort(vector<int> &nums,  int left, int right) {
        if (left >= right)
            return;
        int p = partion(nums, left, right);
        qsort(nums, left, p);
        qsort(nums, p+1, right);
    }     
    void wiggleSort(vector<int> &nums) {
        // write your code here
        vector<int> temp(nums.size());
        qsort(nums, 0, nums.size()-1);
        int s = (nums.size() + 1) >> 1;
        int t = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            temp[i] = (i & 1) == 0 ?  nums[--s] : nums[--t] ;
        }
        nums = temp;
    }
};

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️