专栏首页算法修养LeetCode 324. Wiggle Sort II

LeetCode 324. Wiggle Sort II

题目

这道题目很有意思,有意思的是使用O(n)的时间效率和O(1)的空间效率解决。我会写一篇专业的博客来介绍一下

以下就是O(n)的时间效率和O(1)的空间效率。

class Solution {
public:
int n;
int findKth(vector<int>& nums, int s, int e, int k)
{
    int i = s + 1;
    int j = e;
    int l = s;
    while (i <= j)
    {
        while (i <= j && nums[i] < nums[l])
        {
            i++;
        }

        while (i <= j && nums[j] > nums[l])
        {
            j--;
        }

        if (i <= j)
        {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }

    swap(nums[l], nums[j]);

    if (j - l + 1 == k)
        return nums[j];
    else if (j - l + 1 < k)
    {
        return findKth(nums, j + 1, e, k - (j - l + 1));
    }
    else
        return findKth(nums, s, j - 1, k);
}

double findMid(vector<int>& nums)
{
    if (nums.size() & 1)
    {
        return findKth(nums, 0, nums.size() - 1, nums.size() / 2 + 1);
    }
    else
    {
        int x = findKth(nums, 0, nums.size() - 1, nums.size() / 2);
        int y = findKth(nums, 0, nums.size() - 1, nums.size() / 2 + 1);
        return 1.0 * (x + y) / 2;
    }
}

int getNext(int index)
{
    index -= 2;
    if (index < 0)
    {
        return n + index + (~n & 1) * (~index & 1);
    }

    return index;
}

int getPre(int index)
{
    index += 2;

    if (index >= n)
        return abs((n | 1) - index);

    return index;
}

int compare(int a, int b)
{
    if ((a ^ b) & 1)
    {
        return a & 1;
    }
    else
    {
        return a <= b;
    }
}

void wiggleSort(vector<int>& nums) {

    if (nums.size() <= 1)
        return;
    double mid = findMid(nums);
    
    int i, j, k;
    n = nums.size();
    i = j = (n & 1 ? n - 1 : n - 2);
    k = 1;
    while (compare(k, j))
    {
        if (nums[j] < mid)
        {
            swap(nums[i], nums[j]);
            i = getNext(i);
            j = getNext(j);
        }
        else if (nums[j] == mid)
        {
            j = getNext(j);
        }
        else
        {
            swap(nums[j], nums[k]);
            k = getPre(k);
        }
    }
}

};

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法细节系列(35):不一样的排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode 0324 - Wiggle Sort II

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

    Reck Zhang
  • 牛顿法-LeetCode 319、322、324、331、332、389

    初始时有 n 个灯泡关闭。第 1 轮,你打开所有的灯泡。第 2 轮,每两个灯泡你关闭一次。第 3 轮,每三个灯泡切换一次开关(如果关闭则开启,如果开启则关闭)。...

    算法工程师之路
  • LeetCode 280. Wiggle Sort IIsolution

    复杂度 时间 O(N) 空间 O(1) 思路 题目对摇摆排序的定义有两部分: 如果i是奇数,nums[i] >= nums[i - 1] 如果i是偶数...

    desperate633
  • C#版 - Leetcode 215. Kth Largest Element in an Array-题解

    在线提交: https://leetcode.com/problems/kth-largest-element-in-an-array/

    Enjoy233
  • LeetCode 324. 摆动排序 II

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

    Michael阿明
  • LeetCode 385. 迷你语法分析器(栈)

    我的CSDN博客地址 https://michael.blog.csdn.net/

    Michael阿明
  • ​LeetCode刷题实战324:摆动排序 II

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • Leetcode 922. Sort Array By Parity II

    文章作者:Tyan 博客:noahsnail.com | CSDN | 简书

    Tyan
  • 数组排序问题-LeetCode 905、922、1122、451(哈希表,双指针)

    给定一个非负整数数组 A,返回一个数组,在该数组中, A 的所有偶数元素之后跟着所有奇数元素。 你可以返回满足此条件的任何数组作为答案。

    算法工程师之路
  • 算法学习笔记-回溯

    买唯送忧
  • 双指针,集合问题-LeetCode 344、345、347、349、350

    编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O...

    算法工程师之路
  • Leetcode 题目列表(难度、出现频率、知识点)

    不全,但好像没看到有更好的版本,刷前132题暂时凑合着用吧! 转载自:LeetCode Question Difficulty Distribution ?...

    triplebee
  • 数字问题-LeetCode 263、264、274、275

    思路挺简单的,就是对这个数整除 2 或者整除 3 或者整除 5,然后看最后是不是等于 1。如果不能够整除,那么就 不是丑数了!

    算法工程师之路
  • ​【LeetCode每日一题】179. 最大数

    给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。

    公众号guangcity
  • 数字问题-LeetCode 452、453、454、455、456、459(KMP算法)

    在二维空间中有许多球形的气球。对于每个气球,提供的输入是水平方向上,气球直径的开始和结束坐标。由于它是水平的,所以y坐标并不重要,因此只要知道开始和结束的x坐标...

    算法工程师之路
  • LeetCode 47. 全排列 II(回溯+搜索剪枝)

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

    Michael阿明
  • LeetCode 40. 组合总和 II(排列组合 回溯)

    给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

    Michael阿明
  • GitHub高星!互联网公司最常见的面试算法题大集合

    LeetCode是一个美国的在线编程网站,收集了各个大厂的笔试面试题,对找工作的毕业生和开发者来说,非常有价值。不过LeetCode上面的题目很多都是考察应聘者...

    新智元

扫码关注云+社区

领取腾讯云代金券