《剑指offer-第二版》-面试题03-数组中重复的数字-02-不修改数组找出重复的数字(Java)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《剑指offer-第二版》-面试题03-数组中重复的数字-02-不修改数组找出重复的数字(Java)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2202字，纯文字阅读大概需要4分钟。

内容图文

---

点击查看: 《剑指offer-第2版》 全部面试题 详解目录(Java版）

---

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

题目描述： 在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2 , 3 , 5 , 4 , 3 , 2 , 6 , 7 },那么对应输出的是重复的数字2或3

• 思路一： 复制数组，按照03_01的方法手动排序。 时间O(n) 空间O(n)
• 思路二: 使用hashmap 时间O(n) 空间O(n)
• 思路三: 使用二分查找的思想，因为数字为1-n.
  • 我们把1~n的数字从中间的数字m分为两部分，前面一半为1 ~ m，后面一半为m+1 ~ n。 如果 1 ~ m的数字的数目超过m，那么这一半的区间里一定包含重复数字；否则，另一半 m+1 ~ n 的区间里一定包含重复的数字。我们可以继续把包含重复区间数字的区间一份为二，直到找到一个重复的数字。这个过程和二分查找算法很类似，只是多了一步统计区间里数字的数目。
  • 如果输入长度为n的数组，那么计数函数执行O(logn)次，每次需要O(n)的时间，因此总的时间复杂度为O(nlogn)，空间复杂度为O(1)

注意:

• start end middle 均为数组中最小值，最大值，(max-min)/2+start的值
• 目的是为了找出，某个重复的数字，故是对数组中最大和最小的数字范围进行二分 而非数组区间
  

package ch02;

/**
 * @author Ren
 */
public class T03_2_不修改数组找出重复的数字 {

    public static void main(String[] args) {
        int [] arr = {2,5,4,3,2,6,7};
        int ans = getDuplication(arr,arr.length);
        System.out.println(ans);
    }

    static int getDuplication(int [] arr, int length){
        if(arr==null || length <= 0){
            return -1;
        }
        // 找到数组中的最大值和最小值
        int min=length,max = 1;
        for (int i = 0; i < length; i++) {
            min=min>arr[i]?arr[i]:min;
            max=max<arr[i]?arr[i]:max;
        }
        int start = min;
        int end = max;
        while (end >= start){
            int middle = ((end-start)>>1) + start;
            int count = countRange(arr,length,start,middle);
            // 当start==end 则找到重复的目标，返回数据
            if(end==start){
                if(count>1){
                    return start;
                }else{
                    break;
                }
            }
            // 若 count>(middle-start+1) 该区间（数字大小区间 不是数组的区间）内有重复元素 下次循环的end=middle
            if(count>(middle-start+1)){
                end = middle;
            }else{ // 否则 对后半个区间进行统计  start = middle+1
                start = middle + 1;
            }
        }
        return -1;
    }

    /**
     * 统计区间元素在数组中出现的次数的方法
     */
    static int countRange(int [] arr,int length,int start,int end){
        if(arr==null){
            return 0;
        }
        int counts = 0;
        for (int i = 0; i < length; i++) {
            if(arr[i]>=start && arr[i]<=end){
                counts++;
            }
        }
        return counts;
    }
}

内容总结

以上是互联网集市为您收集整理的《剑指offer-第二版》-面试题03-数组中重复的数字-02-不修改数组找出重复的数字(Java)全部内容，希望文章能够帮你解决《剑指offer-第二版》-面试题03-数组中重复的数字-02-不修改数组找出重复的数字(Java)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---