首页 > 编程语言 >[算法]循环排序

[算法]循环排序

时间:2022-09-19 01:12:34浏览次数:121  
标签:示例 nums int interval length ++ 算法 循环 排序

这类题的特点是给定的数值和下表rank是类似的,其中可能会有一些差异.在设计算法的时候,可以将value值映射到rank上去.

其中,选择大于的值最好 比 rank的最大值+1,这样会避免导致 value % (nums.length)的时候会有同一个值.

 

题目范例:

268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

 

示例 1:

输入:nums = [3,0,1]
输出:2
解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。
示例 2:

输入:nums = [0,1]
输出:2
解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。
示例 3:

输入:nums = [9,6,4,2,3,5,7,0,1]
输出:8
解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。
示例 4:

输入:nums = [0]
输出:1
解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1 是丢失的数字,因为它没有出现在 nums 中。
 

提示:

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二
 

进阶:你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

 

题解:

       public int missingNumber(int[] nums) {

        int len = nums.length + 1;
        for (int i = 0; i < nums.length; i++) {
            int targetRank = nums[i] % len;
            if (targetRank < nums.length) {
                nums[targetRank] += len;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < len) {
                return i;
            }
        }
        return nums.length;

    }

 

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

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

 

示例 1:

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

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

提示:

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
进阶:你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

题解:

   public List<Integer> findDisappearedNumbers(int[] nums) {

        List<Integer> result = new ArrayList<>();
        int interval = nums.length + 1;
        for (int i = 0; i < nums.length; i++) {
            int targetRank = nums[i] % interval - 1;
            nums[targetRank] += interval;
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < interval) {
                result.add(i + 1);
            }
        }
        return result;
    }

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

 

示例 1:

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

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

提示:

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次
 

进阶:

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?

题解:

  public int findDuplicate(int[] nums) {

        int interval = nums.length + 1;
        for (int i = 0; i < nums.length; i++) {
            int targetRank = nums[i] % interval - 1;
            nums[targetRank] += interval;
        }

        int resultRank = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 2 * interval) {
                resultRank = i + 1;
            }
            nums[i] %= interval;
        }
        return resultRank;
    }

 

442. 数组中重复的数据

给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数,并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

 

示例 1:

输入:nums = [4,3,2,7,8,2,3,1]
输出:[2,3]
示例 2:

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

输入:nums = [1]
输出:[]
 

提示:

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
nums 中的每个元素出现 一次 或 两次

 

题解

    public List<Integer> findDuplicates(int[] nums) {

        int interval = nums.length + 1;
        int interval2 = interval * 2;
        for (int i = 0; i < nums.length; i++) {
            int targetRank = nums[i] % interval - 1;
            nums[targetRank] += interval;
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > interval2) {
                result.add(i + 1);
            }
        }
        return result;
    }

 

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 

示例 1:

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

输入:nums = [3,4,-1,1]
输出:2
示例 3:

输入:nums = [7,8,9,11,12]
输出:1
 

提示:

1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

 

题解

    public int firstMissingPositive(int[] nums) {

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 || nums[i] > nums.length) {
                nums[i] = 0;
            }
        }
        int interval = nums.length + 1;
        for (int i = 0; i < nums.length; i++) {
            int target = nums[i] % interval - 1;
            if (target >= 0) {
                nums[target] += interval;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < interval) {
                return i + 1;
            }
        }
        return nums.length+1;
    }

这个题不是直接可以使用 循环排序的算法.需要做一些转换为这种题.

 

总结:

这种题就是使用原本数组的 rank 和value之间的关系.

其中找出 rank和value下标之间转换的时候 可以适用 nums[rank] = nums[rank] + interval .interval选择比 当前序列中元素大一个的值.

这里需要思考返回值的时候可能会出现后一个的值,这种 需要看 rank和value之间的关系. 例如 41返回的是nums.length +1 .而268返回的是nums.lenght.这个当中主要是 rank +1 = value or rank = value的区别.

 

标签:示例,nums,int,interval,length,++,算法,循环,排序
From: https://www.cnblogs.com/xxuuzz/p/16706404.html

相关文章

  • 1636. 按照频率将数组升序排序
    1636.按照频率将数组升序排序给你一个整数数组 nums ,请你将数组按照每个值的频率升序排序。如果有多个值的频率相同,请你按照数值本身将它们降序排序。 请你返......
  • Problem P24. [算法课回溯]组合问题
    采用递归遍历所有可能性,再使用剪枝减小运行时间,利用回溯,代码有注释#include<iostream>#include<bits/stdc++.h>#include<cstdio>#include<string>usingnamespace......
  • 五种基础的最短路算法总结与证明
    朴素版dijkstra:进行n-1次松弛操作,每次都用当前dist最小的点更新,这样就能保证经过了n-1次松弛之后,起点到其他点的距离一定是最短的(On^2)堆优化......
  • 串的模式匹配算法
    一、算法设计思想1.简单模式匹配算法从主串的第一个位置开始和模式串的第一个字符开始比较,相等继续比较下一个字符;否则从主串的下一个字符和模式串的第一个字符重新开始......
  • leetcode 622.设计循环队列
    622.设计循环队列难度中等402  设计你的循环队列实现。循环队列是一种线性数据结构,其操作表现基于FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它......
  • k最近邻算法
    #K最近邻算法##概述K最近邻算法适用于找出距离A坐标最近的几个点,可以用来做推荐系统##计算公式以及模拟K最近邻算法有两个公式:距离公式,相似度公式(余弦)###距离公式......
  • 平滑的加权轮询均衡算法
    前言在反向代理、路由、分布式应用调度等场景中通常都需要用到负载均衡算法,负载均衡的关键要点是“均衡”,即确保调用请求能均衡的落到多个处理节点上,负载均衡算法一般使用......
  • 算法性能分析
    算法的性能分析概括成时间复杂度和空间复杂度两部分;1.时间复杂度通常指算法运行的时间(大O记法只保留最高次项,忽略低次项和常数项)2.空间复杂度......
  • 易语言-99乘法表(四种循环)
    定义变量 定义清楚按钮功能 1、计次循环 2、变量循环 3、判断循环  4、循环判断   最终软件运行界面: ......
  • KMP算法的底层理解
    KMP的主要思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配了。KMP的精髓所在就是前缀表。(下面用next[]数组来表......