leetcode 324. Wiggle Sort II 摇摆排序

ゝ一世哀愁。 2022-06-07 01:09 117阅读 0赞

Given an unsorted array nums, reorder it such that nums\[0\] < nums\[1\] > nums\[2\] < nums\[3\]….

Example:  
(1) Given nums = \[1, 5, 1, 1, 6, 4\], one possible answer is \[1, 4, 1, 5, 1, 6\].  
(2) Given nums = \[1, 3, 2, 2, 3, 1\], one possible answer is \[2, 3, 1, 3, 1, 2\].

Note:  
You may assume all input has valid answer.

Follow Up:  
Can you do it in O(n) time and/or in-place with O(1) extra space?

这道题我直接的做法是先排序，然后依次安排。

代码如下：

import java.util.Arrays;
    
    public class Solution 
    {
        public void wiggleSort(int[] nums) 
        {
            if(nums==null || nums.length<=1)
                return;
            int[] tmp=new int[nums.length];
            for(int i=0;i<nums.length;i++)
                tmp[i]=nums[i];
            Arrays.sort(tmp);
            int i=(nums.length+1)/2,j=nums.length;
            for(int k=0;k<nums.length;k++)
            {
                nums[k]=(k&1)>0? tmp[--j]:tmp[--i];
            }
        }
    }

下面是C++的做法，就是想排序，然后插入即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        void wiggleSort(vector<int>& nums)
        {
            vector<int> a = nums;
            sort(a.begin(), a.end());
            int i = a.size(), j = (a.size() + 1) / 2;
            for (int k = 0; k < a.size(); k++)
                nums[k] = (k % 2 == 0) ? a[--j] : a[--i];
    
        }
    };