C++ solution maybe o(n) time (I am not sure), o(1) space


  • 0
    T
    class Solution {
        public:
            void wiggleSort(vector<int>& nums) {
                int sorted = 0;
                int cur = 1;
                // 1: next one is greater than current sorted last element
                // -1: next one is smaller than the current sorted last element
                int state = 1;
                int pos;
                while (sorted < nums.size() - 1) {
                    if (cur == nums.size()) {
                        cur = sorted + 1;
                    }
                    // if there many elements with the same value between cur and sorted
                    if (cur != sorted + 1) {
                        // skip all element with the same value as sorted
                        while (nums[cur] == nums[sorted]) {
                            cur ++;
                        }
                        // if cur get the end of the array, let it go back to sorted + 1
                        if (cur == nums.size()) {
                            continue;
                        }
                        // if cur does not equals to nums[sorted], we can insert it into
                        // the sorted sequence.
                        if (state == 1) {
                            // the required next one is greater
                            // example 1: 2 5 3 3 4
                            // example 2: 2 5 3 3 2
                            if (nums[cur] > nums[sorted]) {
                                swap(nums[sorted + 1], nums[cur]);
                                sorted += 2;
                            } else {
                                swap(nums[sorted], nums[cur]);
                                sorted ++;
                                state = -1;
                            }
                        } else {
                            // the required next one is smaller
                            // example 1: 2 5 2 4 4 5
                            // example 2: 2 5 2 4 4 1
                            if (nums[cur] > nums[sorted]) {
                                swap(nums[sorted], nums[cur]);
                                sorted ++;
                                state = 1;
                            } else {
                                swap(nums[sorted + 1], nums[cur]);
                                sorted += 2;
                            }
                        }
                        cur ++;
                    } else {
                        // cur = sorted + 1
                        if (state == 1) {
                            // the required next one is greater
                            // example 1: 3 5 2 4
                            // example 2: 3 5 2 1
                            // example 3: 3 5 2 2
                            if (nums[cur] > nums[sorted]) {
                                sorted ++;
                                cur ++;
                                state = -1;
                            } else if (nums[cur] < nums[sorted]) {
                                swap(nums[sorted], nums[cur]);
                                sorted ++;
                                cur ++;
                                state = -1;
                            } else {
                                pos = search(nums, sorted - 2, state, nums[cur]);
                                if (pos != -1) {
                                    swap(nums[pos], nums[cur]);
                                } else {
                                    // if cannot find the appropriate position, just
                                    // increase cur.
                                    cur ++;
                                }
                            }
                        } else {
                            // example 1: 2 5 4 6 1
                            // example 2: 2 5 4 6 7
                            // example 3: 2 5 4 6 6
                            if (nums[cur] < nums[sorted]) {
                                sorted ++;
                                cur ++;
                                state = 1;
                            } else if (nums[cur] > nums[sorted]) {
                                swap(nums[sorted], nums[cur]);
                                sorted ++;
                                cur ++;
                                state = 1;
                            } else {
                                pos = search(nums, sorted - 2, state, nums[cur]);
                                if (pos != -1) {
                                    swap(nums[pos], nums[cur]);
                                } else {
                                    // if cannot find the appropriate position, just
                                    // increase cur.
                                    cur ++;
                                }
                            }
                        } // end of state = -1
                    } // end of cur = sorted + 1;
                }
            }
            int search(vector<int>& nums, int pos, int flag, int value) {
                // find the appropriate pos for condition: cur = sorte + 1, and
                // nums[cur] = num[sorted]
                while (pos >= 0) {
                    if (nums[pos] == value) {
                        pos -= 2;
                    } else {
                        if (flag == 1) {
                            if (pos == 0 || value < nums[pos - 1]) {
                                return pos;
                            } else {
                                pos -= 1;
                                flag = -1;
                            }
                        } else {
                            if (value > nums[pos - 1]) {
                                return pos;
                            } else {
                                pos -= 1;
                                flag = 1;
                            }
                        }
                    }
                }
                return -1;
            }
        };
    
    1. if the adjacent element is not equal, we can swap them and make the sequence wiggle before them.
    2. if the adjacent element is equal, if we can find a appropriate element which already in the wiggle sequence which can be exchange with the equal element, we go back to 1
    3. if cannot find such element, we increase cursor until no such element. We first use the different element insert to the subsequence with the same value, until cur=sorted+1, or cursor comes the end of the arrays.

  • 0

    I didn't look into the details, but I ran some experiments. I inserted this at the start:

            int n = 20000;
            nums.resize(n);
            for (int i=0; i<n; i++)
                nums[i] = 1 - i % 2;
    

    That creates input [1, 0, 1, 0, 1, 0, 1, 0, ...].

    Then I clicked "Run Code" and checked the time. For n=20000, it's about 240 ms. For n=40000, it's about 960 ms. Doubling n quadruples the time, so it looks like quadratic time. What do you think?


  • 0
    T

    Thanks.
    If you input sequence [1, 0, 1, 0, 1, 0....], I am sure about that this algorithm scan the sequence only one time. Because every time the algorithm compare the adjacent two, if them follow the order or swap the adjacent two to follow the order, every element need to be visited only one time.
    The following is my test case with 10 and 20 elements. I print all it procedure:
    10 elements:

    begin: 1 0 1 0 1 0 1 0 1 0
    current: 0 1 1 0 1 0 1 0 1 0
    current: 0 1 1 0 1 0 1 0 1 0
    current: 0 1 0 1 1 0 1 0 1 0
    current: 0 1 0 1 1 0 1 0 1 0
    current: 0 1 0 1 0 1 1 0 1 0
    current: 0 1 0 1 0 1 1 0 1 0
    current: 0 1 0 1 0 1 0 1 1 0
    current: 0 1 0 1 0 1 0 1 1 0
    current: 0 1 0 1 0 1 0 1 0 1
    result: 0 1 0 1 0 1 0 1 0 1

    20 elements:
    begin: 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
    current: 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
    current: 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
    current: 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
    current: 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
    current: 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0
    current: 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0
    current: 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0
    current: 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0
    current: 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0
    current: 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0
    current: 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0
    current: 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0
    current: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0
    current: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0
    current: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0
    current: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0
    current: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0
    current: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0
    current: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
    result: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

  • 0

    But if you cout << pos << endl; in the loop in search, you can see that it runs from the current position all the way back to the start of the vector over and over again. It's clearly quadratic.


  • 0
    T

    Thanks. Yes, I ignored it. What about the average case? Not such special case.


  • 0

    No idea. I'd have to really understand your solution, and I'm not sure what "average case" should mean here.


  • 0
    T

    Ok, thanks. Average case refers to not such special case, and the average runtime time. I will try to calculate it. Thanks~~


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.