java参考桶排序思路

一时失言乱红尘 2024-03-25 10:52 56阅读 0赞

这种排序会把数组变成如下形式：

按照桶排序思路进行预处理：保证 1 出现在 nums\[0\] 的位置上，2 出现在 nums\[1\] 的位置上，…，n 出现在 nums\[n - 1\] 的位置上。

例如样例中 \[4,3,2,7,8,2,3,1\] 将会被预处理成 \[1,2,3,4,3,2,7,8\]。

for(int i = 0; i < n; i++){
                while(nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]){
                    swap(nums, i, nums[i] - 1);
                }
            }

448. 找到所有数组中消失的数字

给你一个含 `n` 个整数的数组 `nums` ，其中 `nums[i]` 在区间 `[1, n]` 内。请你找出所有在 `[1, n]` 范围内但没有出现在 `nums` 中的数字，并以数组的形式返回结果。

输入：nums = [4,3,2,7,8,2,3,1]
    输出：[5,6]

class Solution {
        public List<Integer> findDisappearedNumbers(int[] nums) {
            int n = nums.length;
            for(int i = 0; i < n; i++){
                while(nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]){
                    swap(nums, i, nums[i] - 1);
                }
            }
            List<Integer> ans = new ArrayList<>();
            for(int i = 0; i < n; i++){
                if(nums[i] != i + 1) ans.add(i + 1);
            }
            return ans;
        }
    
        void swap(int[] nums, int a, int b){
            int c = nums[a];
            nums[a] = nums[b];
            nums[b] = c;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，56人围观）

还没有评论，来说两句吧...

相关阅读

相关 java参考桶排序思路

这种排序会把数组变成如下形式：按照桶排序思路进行预处理：保证 1 出现在 nums\[0\] 的位置上，2 出现在 nums\[1\] 的位置上，…，n 出现在 nums\

一时失言乱红尘/ 2024年03月25日 10:52/ 0 赞/ 57 阅读

相关 Java-桶排序(计数排序&基数排序)

桶排序是非基于比较排序的计数排序(非负十进制):先准备十个队列然后按个位数字进桶桶排序是一种思想:一个坑好几个萝卜计数排序的思想很简单:员工的年龄(18-35),

本是古典何须时尚/ 2023年10月08日 21:55/ 0 赞/ 33 阅读

相关基数排序（桶排序）思路整理

首先了解一下什么是基数排序：基数排序是桶排序的扩展，不了解桶排序也没有关系。它是通过待排序列中每个值的各个位，将每个值按照一定规则放置“桶”中，达到排序的效果。（刚刚接触

た入场券/ 2023年02月18日 03:16/ 0 赞/ 26 阅读

相关 java 桶排序

-------------------- java 桶排序 \\\\\\\\\\\\\\\\\\\\\\\ 桶排序

灰太狼/ 2022年11月21日 09:44/ 0 赞/ 131 阅读

相关桶排序java

桶排序把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况

骑猪看日落/ 2022年06月06日 08:07/ 0 赞/ 148 阅读

相关桶排序

期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有 5个同学，这 5个同学分别考了 5分、3分、 5分、2分和 8分，哎考得真是惨不忍睹（满分是 10分）

ゝ一纸荒年。/ 2022年06月02日 06:10/ 0 赞/ 226 阅读

相关 Java实现桶排序

桶排序：使用额外空间，以空间换时间思想，，因此时间复杂度为O(n+m) 1.1 基本思想桶排序是所有排序算法中最快、也是最简单的排序算法。基本思想是在知道所有待排元素的

绝地灬酷狼/ 2022年05月09日 13:40/ 0 赞/ 164 阅读

相关桶排序

include <stdio.h> void swap(int a, int b) { int temp

叁歲伎倆/ 2022年04月23日 01:34/ 0 赞/ 227 阅读

相关桶排序

适用范围桶排序可用于最大最小值相差较大的数据情况，比如\[9012,19702,39867,68957,83556,102456\]。但桶排序要求数据的分布必须均匀

╰半夏微凉°/ 2022年04月18日 03:11/ 0 赞/ 209 阅读

相关桶排序

如我这几天的风格一样，概念不多说，直接正题： >: 桶排序不是基于比较的排序，最好的时间复杂度可以达到O(n)，例如：9个数 10,20,30,40,50,60,70

女爷i/ 2022年03月20日 01:42/ 0 赞/ 288 阅读