Sorting based reverse order assigning


  • 6

    After seeing many post, I do think the best way is to sort and then assign the sorted array interleaving.

    The trap is the there may be duplicate for the median. So, we should assign the max value first to avoid the

    duplicate to happen together.

    The case like this:

        4 5 5 6
    

    If in the original order , the result will be

        4  5  5   6
    

    In the reverse order , the result will be

       5   6  4  5
    

    Here is the code :

      class Solution {
        public:
            void wiggleSort(vector<int>& nums) {
                int len=nums.size();
                if(len<=1) return;
                sort(nums.begin(), nums.end());
                vector<int> result(nums);
                int j=len-1;
                for(int i=1; i<len; i+=2, j--) result[i]=nums[j];
                for(int i=0; i<len; i+=2, j--) result[i]=nums[j];
                nums=result;
                return;
            }
        };
    

    Update:

    About how to find the k-th element of the unordered array , here is the implementation ....

    class Solution {
    public:
        /*
         * param k : description of k
         * param nums : description of array and index 0 ~ n-1
         * return: description of return
         */
        int kthLargestElement(int k, vector<int> nums) {
            int left = 0, right = nums.size() - 1;
            //default_random_engine gen((random_device())());
            while (left <= right) {
                // Generates a random int in [left, right].
                //uniform_int_distribution<int> dis(left, right);
                int pivot_idx = left;
                int new_pivot_idx = PartitionAroundPivot(left, right, pivot_idx, nums);
                if (new_pivot_idx == k - 1) {
                    return nums[new_pivot_idx];
                } else if (new_pivot_idx > k - 1) {
                    right = new_pivot_idx - 1;
                } else {  // new_pivot_idx < k - 1.
                    left = new_pivot_idx + 1;
                }
            }
        }
    
        // Partition nums[left : right] around pivot_idx, returns the new index of the
        // pivot, new_pivot_idx, after partition. After partitioning,
        // nums[left : new_pivot_idx - 1] contains elements that are greater than the
        // pivot, and nums[new_pivot_idx + 1 : right] contains elements that are less
        // than the pivot.
        int PartitionAroundPivot(int left, int right, int pivot_idx, vector<int>& nums) {
            int pivot_value = nums[pivot_idx];
            int new_pivot_idx = left;
            swap(nums[pivot_idx], nums[right]);
            for (int i = left; i < right; ++i) {
                if (nums[i] > pivot_value) {
                    swap(nums[i], nums[new_pivot_idx++]);
                }
            }
            swap(nums[right], nums[new_pivot_idx]);
            return new_pivot_idx;
        }
    };

  • 0
    C

    Sorting is O(nlogn), not O(n).


Log in to reply
 

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