当前位置: 首页 > article >正文

[算法] [leetcode-324] 摆动排序 II

324 摆动排序 II

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

你可以假设所有输入数组都可以得到满足题目要求的结果。

示例 1:

输入:nums = [1,5,1,1,6,4]
输出:[1,6,1,5,1,4]
解释:[1,4,1,5,1,6] 同样是符合题目要求的结果,可以被判题程序接受。
示例 2:

输入:nums = [1,3,2,2,3,1]
输出:[2,3,1,3,1,2]

提示:

1 <= nums.length <= 5 * 104
0 <= nums[i] <= 5000
题目数据保证,对于给定的输入 nums ,总能产生满足题目要求的结果

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


 class Solution {
        public void wiggleSort(int[] nums) {
            // 保证 1/2length下标有序 完成荷兰国旗问题
            chessSort(nums);
            // 6  --- 3
            // 7 --- 3
           int mid = nums.length %2 ==1 ? (nums.length/2+1) : (nums.length/2);
            // int mid = nums.length/2;
            int smallIndex = mid-1;
            int midIndex = nums.length - 1;
            int index = 0;
            int [] result = new int[nums.length];
            while(smallIndex >=0 && midIndex >= mid){
                result[index++] = nums[smallIndex--];
                result[index++] = nums[midIndex--];
            }
            if(index == nums.length -1){
                if(smallIndex >= 0) {
                    result[index++] = nums[smallIndex++];
                } else {
                    result[index++] = nums[midIndex++];
                }
            }
            index =0;
            while (index<nums.length){
                nums[index] = result[index];
                index++;
            }
        }

        public void swap(int []nums, int begin, int end){
            int tmp = nums[begin];
            nums[begin] = nums[end];
            nums[end] = tmp;
        }

        public void chessSort(int[] nums){
            int mid = nums.length /2;
            int begin = 0;
            int end = nums.length -1;
            while (begin <= end) {
                int[] range = chessSortPartition( nums,  begin, end);
                if(range[0] <= mid && range[1]>=mid){
                    break;
                } else if (range[0] > mid){
                    end = range[0] -1;
                }else if(range[1] < mid){
                    begin = range[1] +1;
                }
            }
        }

        public int[] chessSortPartition(int[] nums, int begin, int end){
            if(begin > end){
                return new int[]{-1,-1};
            }
            if(begin == end){
                return new int[]{begin,begin};
            }
            int randNum = nums[(begin + new Random().nextInt(end-begin+1))];
            int beginIndex = begin -1;
            int endIndex = end +1;
            int index = begin;
            while(index<endIndex){
                if(nums[index] == randNum){
                    index++;
                } else if(nums[index]<randNum){
                    beginIndex++;
                    swap(nums, index, beginIndex);
                    index++;
                } else {
                    endIndex --;
                    swap(nums, index, endIndex);
                    index = index;
                }
            }
            return new int[]{beginIndex+1,endIndex-1};
        }

    }

http://www.kler.cn/a/463786.html

相关文章:

  • 深入理解 JVM 的垃圾收集器:CMS、G1、ZGC
  • ArcgisServer过了元旦忽然用不了了?许可过期
  • 什么是.net framework,什么是.net core,什么是.net5~8,版本对应关系
  • 设计心得——流程图和数据流图绘制
  • 数字货币支付系统开发搭建:构建未来的区块链支付生态
  • Codigger集成Copilot:智能编程助手
  • 【C#】C#打印当前时间以及TimeSpan()介绍
  • uniapp——App下载文件,打开文档(一)
  • DeepSeek LLM通过长期主义扩展开源语言模型
  • python基础004--flask
  • python实现自动登录12306抢票 -- selenium
  • JavaSpring AI与阿里云通义大模型的集成使用Java Data Science Library(JDSL)进行数据处理
  • 上传第三方jar包到maven私服仓库的两种方法
  • 逆向生成原理
  • CSS系列(40)-- Container Queries详解
  • 第8章 汇编语言--- 循环结构
  • SQL语句 相关学习
  • 接口测试Day04-postman生成测试报告ihrm项目
  • 深度剖析 Android Animation 框架
  • android10 audio音量曲线
  • SpringBoot 新特性
  • 使用Windows和FFmpeg 将https://xxx.com/xx.m3u8 推流到B站
  • 二十三种设计模式-建造者模式
  • 【2024年-12月-31日-开源社区openEuler实践记录】virtCCA_sdk:开启虚拟化安全增强的编程新钥
  • Maven 测试和单元测试介绍
  • 项目管理:用甘特图 “导航” 项目全程