2 lines neat Python


  • 17
    def wiggleSort(self, nums):
        for i in range(len(nums)):
            nums[i:i+2] = sorted(nums[i:i+2], reverse=i%2)

  • -1
    B

    My original post: @StefanPochmann Very neat! Here's the C++ version for other users' reference, it is an nlogn algorithm because of the sorting.

    void wiggleSort(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            for (int i=1; i+1<nums.size(); i+=2) {
                swap(nums[i],nums[i+1]);
            }
        }
    

    So that was wrong, I didn't understand the original post. Here's my second attempt of making a c++ version of the logic, it is really O(N). The sorting section only has 2 elements, so O(log(2))=O(1).

    void wiggleSort(vector<int>& nums) {
            for (int i=0; i+1<nums.size(); i++) {
                if (i%2) sort(nums.begin()+i,nums.begin()+i+2,greater<int>());
                else sort(nums.begin()+i,nums.begin()+i+2);
            }
        }
    

  • 0

    the reverse=i%2 thing is really brilliant! learned the trick.


Log in to reply
 

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