06：不修改数组找出重复的数字

傷城~ 2023-02-21 12:56 209阅读 0赞

#### 不修改数组找出重复的数字 ####

要求：在一个长度为n+1的数组，数组内值为1~n，不能修改原本数组  
思路：使用分治思维，在一个长度为n+1的数组，数组内值为1~n的情况下，必定存在数据重复情况。我们不在数组上做文章，将焦点聚集在1-n的数值上。  
将数值1-n分为两部分\[1，(n+1)/2\]，\[(n+1)/2+1，n\]，统计两部分数值在数组中出现的次数，若大于数值的个数，则必定重复，后续重复即可。  
**例如：** 数组\[1,2,3,4,5,3\]，数值为1-5，我们将数值分为\[1，2，3\]和\[4，5\]，统计\[1，2，3\]在数组中出现的次数。若大于3次则必定存在重复。

public class Offer06 { 
        public static void main(String[] args) { 
            int[] arr = new int[]{ 1,2,3,4,5,3};
            int start = 1;
            int end = arr.length;
            //分治
            while (start<end){ 
                int middle = (start + end)/2;
                int count = 0;
                //计数
                for (int i=0;i<arr.length;i++){ 
                    if(arr[i]>=start&&arr[i]<=middle)count++;
                }
                //判断计数情况
                if(count>middle-start+1){ 
                    end = middle;
                }else{ 
                    start = middle+1;
                }
            }
            System.out.println(end);
        }

发表评论取消回复

表情：

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

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

相关阅读

相关图解面试题：找出数组中重复的数字？

![format_png][] 今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题03. 数组中重复的数字。题目链接：https://lee

忘是亡心i/ 2023年10月05日 09:33/ 0 赞/ 70 阅读

相关 ACWing-剑指Offer-不修改数组找出重复的数字

题目链接：[https://www.acwing.com/problem/content/description/15/][https_www.acwing.com_probl

ゞ浴缸里的玫瑰/ 2023年07月21日 08:57/ 0 赞/ 29 阅读

相关 06：不修改数组找出重复的数字

不修改数组找出重复的数字要求：在一个长度为n+1的数组，数组内值为1~n，不能修改原本数组思路：使用分治思维，在一个长度为n+1的数组，数组内值为1~n的情况下，

傷城~/ 2023年02月21日 12:56/ 0 赞/ 210 阅读

相关 186-找出数组中的重复数字

题目如下：给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个

布满荆棘的人生/ 2022年10月29日 12:27/ 0 赞/ 298 阅读

相关 AcWing 14. 不修改数组找出重复的数字（C++）- 数组作哈希

题目链接：[https://www.acwing.com/problem/content/description/15/][https_www.acwing.com_probl

女爷i/ 2022年09月11日 14:11/ 0 赞/ 171 阅读

相关找出数组中重复的元素

注意：找出数组中重复的元素，数组中也有可能不存在重复的数，也有可能存在多个方法一：使用位图法，再申请一个数组b，用b\[a\[i\]\]存储a\[i\]的重复次数：

灰太狼/ 2022年05月25日 05:38/ 0 赞/ 274 阅读

相关找出数组中重复的数字

【题目】在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字

￡神魔★判官ぃ/ 2022年05月22日 12:35/ 0 赞/ 283 阅读

相关不修改数组找出重复的数字

不修改数组找出重复的数字在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。从数组中找出任意一个重复的数字，但不能修改输入

ゝ一世哀愁。/ 2022年04月24日 13:52/ 0 赞/ 273 阅读

相关 java 找出重复的数字

这是一个经典的题型，比如：有1亿个数字，找出其中重复的。最直观的写法就是双重循环了，但是效率过低。再就是先排序再遍历，又总感觉不太直接。后来偶然查到BitSet有相应的ap

旧城等待，/ 2021年09月24日 12:32/ 0 赞/ 393 阅读

相关《剑指offer刷题笔记》 2、不修改数组找出重复的数字【c++详细题解】

题目给定一个长度为 n + 1 n+1 n\+1 的数组`nums`，数组中所有的数均在 1 ∼ n 1∼n 1∼n 的范围内，其中 n ≥ 1 n≥1 n≥

野性酷女/ 2021年07月25日 00:29/ 0 赞/ 328 阅读