专栏首页Michael阿明学习之路LeetCode 324. 摆动排序 II

LeetCode 324. 摆动排序 II

1. 题目

给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

示例 1:
输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:
输入: nums = [1, 3, 2, 2, 3, 1]
输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
说明:
你可以假设所有输入都会得到有效的结果。

进阶: 你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗?

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/wiggle-sort-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • copy副本,先排序,然后对前半段逆序,对后半段逆序
  • 然后前后两段数据,交叉写回原数组
  • 时间复杂度
O(nlogn)

, 空间复杂度

O(n)
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> temp(nums);//副本
        int n = (nums.size()+1)/2, len = nums.size();
        sort(temp.begin(), temp.end());//排序
        reverse(temp.begin(), temp.begin()+n);//前半段逆序
        reverse(temp.begin()+n, temp.end());//后半段逆序
        int i = 0, j = n, k = 0;
        while(k < len)
        {
        	nums[k++] = temp[i++];//第一段的一个数据
        	if(k < len)//防止奇数情况进来越界
        		nums[k++] = temp[j++];//第二段的一个数据
        }
    }
};

or 反转操作省掉,直接倒着交叉写回

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        vector<int> temp(nums);
        int n = (nums.size()+1)/2, len = nums.size();
        sort(temp.begin(), temp.end());
        int i = n-1, j = len-1, k = 0, idx = 0;
        while(k < len)
        {
        	nums[idx++] = temp[i--];
            k++;
        	if(k < len)
            {
                nums[idx++] = temp[j--];
                k++;
            }
        }
    }
};

求高人解答:你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗?

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员面试金典 - 面试题 17.19. 消失的两个数字(数学/位运算)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/missing-two-lcci 著作权归领扣网络所...

    Michael阿明
  • LeetCode 628. 三个数的最大乘积

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-product-of-three-nu...

    Michael阿明
  • LeetCode 223. 矩形面积

    Michael阿明
  • 从零打卡leetcode之day 1--两数之和

    不过心里才两个循环时间复杂度可是n的平方,心想肯定得超时,不过还是大胆提交一下提交,呵呵,居然通过了。。。。

    帅地
  • 【LeetCode-解题一 求和】

    Given an array of integers, return indices of the two numbers such that they add...

    用户5640963
  • Leetcode 16. 3Sum Closest

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 算法训练营-第一周-数组链表

    栈是一种线性逻辑结构,栈的元素只能后进先出。最早进入的元素存放的位置叫做栈底,最后进入的元素存放的位置叫栈顶。

    编程之心
  • LeetCode 每日一题169: 求众数

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    benny
  • LeetCode :1.两数之和 解题报告及算法优化思路

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    若羽
  • 数字问题-LeetCode 462、463、473、474、475、476、477、482(二分)

    LeetCode # 462 463 473 474 475 476 477 482

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券