LeetCode 精选 TOP 面试题（Java 实现）—— 变异版寻找重复数

最新推荐文章于 2024-05-07 15:56:26 发布

杨小帆_

最新推荐文章于 2024-05-07 15:56:26 发布

阅读量306

点赞数

分类专栏： LeetCode精选Top面试题文章标签：算法 java 面试数据结构

本文链接：https://blog.csdn.net/qq_40697071/article/details/104372008

版权

LeetCode精选Top面试题专栏收录该内容

78 篇文章

订阅专栏

本文详细解析了一种变异版寻找重复数的算法，针对包含n+1个整数的数组，数字范围在1到n之间，通过优化的解题思路和BitSet数据结构的应用，实现了高效查找所有重复数的功能。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

文章目录

一、题目描述

1.1 题目

变异版寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数，找出所有重复数。

示例 1:

输入: = 4,5,7,1,4,6,5
输出: = 4 5

1.2 知识点

数组

二、解题思路

2.1 解题思路

跟《剑指Offer》寻找重复数题目的思路相似。

2.2 优化思路

可将 int 数组优化为 BitSet

2.3 类似题型

《剑指Offer》数组中重复的数字（Java 实现）

三、实现代码

3.1 代码实现

import java.util.*;
public class Main {
    public static void main(String[] args) {
        
        ArrayList<Integer> ret = new ArrayList<>();
        int[] arr = new int[]{4,5,7,1,4,6,5};
        for(int i = 0; i < arr.length; i++){
            while(arr[i] != i+1){
                if(arr[arr[i]-1] == arr[i]){
                    ret.add(arr[i]);
                    break;
                } else {
                    swap(arr, i, arr[i]-1);
                }
            }
        }
        
        for(int i = 0; i < ret.size(); i++)
            System.out.print(ret.get(i) + " ");
    }
    
    private static void swap(int[] arr, int i1, int i2){
        int temp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = temp;
    }
}