摆动排序 II · Wiggle Sort II（partition）

链接题解1.先用partition函数求解第n/21元素求得下标n/2的位置的排序2.第一个元素填写结果集合pivlot写然后选取首尾指针奇数选择1和length-1偶数选择为1和length-2)3.重新更新l 2 r - 2 填充 结果集合或者partition替换为nth_element(nums.begin(), nums.begin()k/2, nums.end());nums.begin()k/2,已经是求解下标位置class Solution { public: void wiggleSort(vectorint nums) { const int n nums.size(); if (n 1) return; // 1. 拷贝一份用快速选择找中位数 vectorint tem nums; // 如果是奇数 5 , 4, 3, 2, 1 // 求解mid是为5/2 1 第3小的数字是3 // 如果是偶数求解4, 3, 2, 1 // 求解mid是4/21 第3小的数字是2 partition(tem, 0, n - 1, n / 2 1); int mid tem[n / 2]; // 2. 构造答案数组初始全部填中位数 vectorint ans(n, mid); // 3. l 指向第一个奇数位放大值r 指向最后一个偶数位放小值 int l 1; int r (n % 2 0) ? n - 2 : n - 1; // 如果是奇数的化r n-1 // 如果是偶数的化r n-2 4 3 2 1,把2排除 2 4 1 3 for (int i 0; i n; i) { if (nums[i] mid) { ans[r] nums[i]; r - 2; } else if (nums[i] mid) { ans[l] nums[i]; l 2; } // 等于 mid 的不动保持初始的 mid } nums std::move(ans); } private: // 大的在左边从大到小 void partition(vectorint nums, int start, int end, int k) { if (start end) { return; } int pivot nums[start (end - start) / 2]; int left start; int right end; while (left right) { while (left right nums[left] pivot) { left; } while (left right nums[right] pivot) { --right; } if (left right) { swap(nums[left], nums[right]); left; --right; } } if (start k - 1 right) { return partition(nums, start, right, k); } if (start k - 1 left) { return partition(nums, left, end, k - (left - start)); } } };class Solution { public: void wiggleSort(vectorint nums) { const int n nums.size(); if (n 1) return; // 1. 拷贝一份用快速选择找中位数 vectorint tem nums; //int mid partition(tem, 0, n - 1, n / 2); auto mid_it nums.begin() n / 2; nth_element(nums.begin(), mid_it, nums.end()); int mid *mid_it; // 2. 构造答案数组初始全部填中位数 vectorint ans(n, mid); // 3. l 指向第一个奇数位放大值r 指向最后一个偶数位放小值 int l 1; int r (n % 2 0) ? n - 2 : n - 1; for (int i 0; i n; i) { if (nums[i] mid) { ans[r] nums[i]; r - 2; } else if (nums[i] mid) { ans[l] nums[i]; l 2; } // 等于 mid 的不动保持初始的 mid } nums std::move(ans); } };1.先用partition函数求得n/2的位置的排序2.然后选取首尾指针奇数选择1和length-1偶数选择为1和length-2进行swap交换3.每次首指针每次2尾指针每次-2九章算法 - 帮助更多程序员找到好工作硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧这段代码没有通过class Solution { public: /** * param nums: A list of integers * return: nothing */ void wiggleSort(vectorint nums) { // write your code here if (nums.size() 1) { return; } int len nums.size(); kthLargestElement(len/2, nums); if (len % 2 0) { int left 1; int right nums.size()-2; while (left right) { swap(nums[left], nums[right]); left 2; right - 2; } } else { int left 1; int right nums.size() - 1; while (left right) { swap(nums[left], nums[right]); left 2; right - 2; } } } private: int kthLargestElement(int k, vectorint nums) { cout k k endl; // write your code here if (nums.size() 0) { return 0; } int left 0; int right nums.size()-1; int mid partition(nums, left, right); //cout mid mid endl; while (mid ! k-1) { //cout mid mid endl; if (mid k) { right mid; } else { left mid; } mid partition(nums, left, right); } return nums[mid]; } int partition(std::vectorint nums, int left, int right) { int index random() % (right-left1); swap(nums[right], nums[leftindex]); int nSmall left - 1; for (; left right; left) { if (nums[left] nums[right]) { nSmall; swap(nums[left], nums[nSmall]); } } nSmall; swap(nums[right], nums[nSmall]); cout nSmall val nums[nSmall] endl; return nSmall; } };class Solution { public: // O(n)时间复杂度O(1)空间 void wiggleSort(vectorint nums) { if (nums.size() 0) { return; } /*for (auto num : nums) { cout num ; } cout endl;*/ int len nums.size(); // 求得第几大的位置 // 0 1 2 3/2 1假设3个数字就是求得第2大的数字位置 // 0, 1, 2, 3 4/2 2假设4个个数字就是求得第3大的数字位置 partition(nums, 0, len-1, len/21); /*for (auto num : nums) { cout num yyy ; }*/ int left 0; int right len-1; // 如果是奇数的情况把右边的数字排出下 if (len % 2) { --right; } // 原地交换 while (left right) { // 交换 swap(nums[left], nums[right]); // 空出一个位置不需要交换 left 2; right - 2; } /*for (auto num : nums) { cout num ; } cout endl; std::vectorint result; result.reserve(len); int left 0; int right len-1; while (left right) { if (left right) { result.push_back(nums[left]); } else { result.push_back(nums[left]); result.push_back(nums[right]); } left; --right; } nums std::move(result);*/ } private: int partition(std::vectorint nums, int start, int end, int k) { if (start end) { return start; } int val nums[start(end-start)/2]; int l start; int r end; //cout l val r endl; while (l r) { while (l r nums[l] val) { //cout nums endl; l; } while (l r nums[r] val) { //cout nums endl; --r; } if (l r) { swap(nums[l], nums[r]); //cout left : l nums[l] right: r nums[r] endl; l; --r; } } if (start k - 1 r) { return partition(nums, start, r, k); } if (start k - 1 l) { return partition(nums, l, end, k - (l - start)); } return r 1; } };. - 力扣LeetCode