Wiggle Sort

Question:
http://www.lintcode.com/en/problem/wiggle-sort/
Given an unsorted array nums, reorder it in-place such that
nums[0] <= nums[1] >= nums[2] <= nums[3]....
Example
Given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

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> sort = nums;
        int len = nums.size();
        qsort(sort, 0, len-1);
        int l = 0;
        int r = len - 1;
        nums.clear();
        while (l < r) {
          nums.push_back(sort[l]);
          nums.push_back(sort[r]);
          l++;
          r--;
        }
        if (l == r)
          nums.push_back(sort[l]);
    }
};

❤️ 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 ❤️