【LeetCode & 劍指offer 刷題筆記】目錄（持續更新中...）

Wiggle Sort II Given an unsorted array?nums, reorder it such that?nums[0] < nums[1] > nums[2] < nums[3].... Example 1: Input: nums = [1, 5, 1, 1, 6, 4]Output: One possible answer is [1, 4, 1, 5, 1, 6]. Example 2: Input: nums = [1, 3, 2, 2, 3, 1]Output: 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?

---

C++ //問題：擺動排序，a[0] < a[1] > a[2] < a[3]... //？？沒看懂，以后再看 //方法二：利用快排中一步（nth_element函數）將序列分成兩段，以中值為樞軸，從各段段首（或段尾）開始選數 //思路解析：假設排序后為a1 a2...an mid b1 b2...bn,則組織為a1 b1 a2 b2... //此法時間復雜度為O（n）,如果沒有O(1)的空間復雜度，比較簡單，正是這個限制增加了復雜度 class Solution { public: ??? void wiggleSort(vector<int>& nums) { ??????? int m = nums.size(); ??????? auto mptr = nums.begin() + (m-1)/2; ??????? nth_element(nums.begin(), mptr, nums.end()); ??????? int median = *mptr; ??????? int i = 1;?? // position for the larger values: start with first odd index ??????? int j = ((m - 1) & 1) ? m - 2 : m - 1;? // position for the smaller values: start with last even index ??????? for (int l = 0; l < m; ++l) { ??????????? if (nums[l] > median) {? // fill the large element ??????????????? if (l <= i && (l & 1)) continue;?????? // skip the elements which are? already checked: 1, 3, 5, ..., i ??????????????? swap(nums[l--], nums[i]); ??????????????? i += 2; ??????????? } else if (nums[l] < median) {? // fill the smaller element ??????????????? if (l >= j && (l & 1) == 0) continue;???? // skip the elements whcih are checked: j, j + 2, ..., lastEvenIndex ??????????????? swap(nums[l--], nums[j]); ??????????????? j -= 2; ??????????? } ?????? } ??? } }; //方法一：排序后，分成兩段，從各段末尾依次取數（可以避免相等數弄在一起） //不過此法的時間復雜度為O(nlogn)，空間復雜度為O(n),不滿足題意 //思路解析：假設排序后為a1 a2...an b1 b2...bn,則組織為an bn an-1 bn-1... class Solution { public: ??? void wiggleSort(vector<int>& a) ??? { ??????? int n = a.size(); ??????? sort(a.begin(),a.end()); ??????? if(n<=2) return; //小于兩個元素時，直接退出 ?????? ??????? vector<int> temp = a;? ??????? int i = 0, j=(n-1)/2, k=n-1; //i用來遍歷a, j用來遍歷temp第一段（從末尾開始），k用來遍歷第二段。 ??????? for(i = 0; i < n; i++) ??????? { ??????????? a[i] = (i&1)? temp[k--]:temp[j--];//如果i為奇數,取第二段的數（較大），如果為偶數，取第一段的數（較小） ??????????? //注：當n為奇數時，兩段長度不等，第一段比第二段多1，但是上述等式可以保證最后一個數a[n-1]選擇temp[0] ??????? } ??? } }; /* //擺動排序，a[0] < a[1] > a[2] < a[3]... //要得到O(n)時間復雜度，O(1)空間復雜度，可以借鑒wiggle sort I（a[0] <= a[1] >= a[2] <= a[3]...）中的思路 //i為奇數時，a[i]>a[i-1], 偶數時，a[i]<a[i-1], 根據這一規律，遍歷整個序列，不符合則交換 //測試結果表明，對于序列中有多個連續相等數時，此方法不行，因為按照交換策略，相等的數會交換，但是交換后并不會滿足 //i為奇數時，a[i]>a[i-1], 偶數時，a[i]<a[i-1]的規律，而是仍然相等。 class Solution { public: ??? void wiggleSort(vector<int>& a) ??? { ??????? int n = a.size(); ??????? if(n <= 1) return; //元素個數少于1個時，退出 ??????? ??????? for(int i = 1; i < n; i++) ??????? { ??????????? if((i%2 == 1 && a[i]<=a[i-1]) || (i%2 == 0 && a[i]>=a[i-1])) ??????????? { ??????????????? swap(a[i], a[i-1]);//如果不符合擺動規律則交換 ??????????? } ??????? } ??? } }; */ Wiggle Sort I Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3].... For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4]. ? 這道題讓我們求擺動排序，跟Wiggle Sort II相比起來，這道題的條件寬松很多，只因為多了一個等號。由于等號的存在，當數組中有重復數字存在的情況時，也很容易滿足題目的要求。這道題我們先來看一種時間復雜度為O(nlgn)的方法，思路是先給數組排個序，然后我們只要每次把第三個數和第二個數調換個位置，第五個數和第四個數調換個位置，以此類推直至數組末尾，這樣我們就能完成擺動排序了，參見代碼如下： //解法一： // Time Complexity O(nlgn) class Solution { public: ??? void wiggleSort(vector<int> &nums) { ??????? sort(nums.begin(), nums.end()); ??????? if (nums.size() <= 2) return; ??????? for (int i = 2; i < nums.size(); i += 2) { ??????????? swap(nums[i], nums[i - 1]); ??????? } ??? } }; 這道題還有一種O(n)的解法，根據題目要求的nums[0] <= nums[1] >= nums[2] <= nums[3]....，我們可以總結出如下規律： 當i為奇數時，nums[i] >= nums[i - 1] 當i為偶數時，nums[i] <= nums[i - 1] 那么我們只要對每個數字，根據其奇偶性，跟其對應的條件比較，如果不符合就和前面的數交換位置即可，參見代碼如下： //解法二： // Time Complexity O(n) class Solution { public: ??? void wiggleSort(vector<int> &nums) { ??????? if (nums.size() <= 1) return; ??????? for (int i = 1; i < nums.size(); ++i) { ??????????? if ((i % 2 == 1 && nums[i] < nums[i - 1]) || (i % 2 == 0 && nums[i] > nums[i - 1])) { ??????????????? swap(nums[i], nums[i - 1]); ??????????? } ??????? } ??? } }; 來源：http://www.cnblogs.com/grandyang/p/5177285.html

?

轉載于:https://www.cnblogs.com/wikiwen/p/10225971.html

總結

以上是生活随笔為你收集整理的【LeetCode 剑指offer刷题】查找与排序题14：Wiggle Sort（系列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。