在1001个整数的数组中找重复的数

68 阅读 0 评论 45 点赞

我是靠谱客的博主欣喜自行车，最近开发中收集的这篇文章主要介绍在1001个整数的数组中找重复的数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一个共1001个整数的数组，存储的数据范围是【1，1000】。
也就是说，其中有（至少1个）1个数是重复的，现在要求找到那个数，返回其所在的索引（在数组中的索引）。
现在只考虑：仅仅有1个整数重复时，找出那个整数所对应的索引。应该是2个不同的索引。

import java.util.HashMap;

/**
 * 共1001个整数的数组，存储的数据的范围是【1,1000】
 * 其中有1个数是重复的，找出那个重复的数。
 * 返回的是这个数所在的索引。
 * @author Feng
 * 2018年9月13日下午5:45:44
 */
public class Array4 {

    public static int[] demo(int[] arr) {

        int[] res = new int[2];

        if( arr.length <= 1 || arr == null)
            throw new IllegalArgumentException("arg is exception");

        if(arr.length == 2 && arr[0] == arr[1]) {
            return new int[] {0,1};
        }


        // V为索引，K为1-1000
        // 使用的思想还是：HashMap的去除重复。
        /*
         * 直接判断map中是否含有该数组中的某一个元素，如果不包含，就把该数put进去当做Key，索引当做Value。
         * 如果，包含那就更简单了，获取到该元素对应的Value，也就是索引，存入res数组中。
         * 并且，当前的索引i也正是重复位置的索引，将其也存放在res中。
         */
        HashMap<Integer, Integer> map = new HashMap<>(arr.length);
        for(int i = 0; i < arr.length; i ++) {
            if(! map.containsKey(arr[i])) {
                map.put(arr[i], i);
            } else {
                res[0] = map.get(arr[i]);
                res[1] = i;
            }
        }
        return res;
    }

    /**
     * 给整型数组arr中，插入从start到end（包括start，不包括end）的整数。
     * @param start
     * @param end
     * @param arr
     */
    public static void insertNum(int start, int end, int[] arr) {
        if(start > end) return; 

        for(int i = start; i < end && end <= arr.length; i++){
            arr[i] = i + 1;
        }
    }

    // 打印数组的方法。
    public static void print(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            System.out.println("arr[" + i + "] = " + arr[i]);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[1001];
        // 首先，是将数存进数组，用来对方法的测试。
        insertNum(0, 990, arr);
        insertNum(990, 1000, arr);
        arr[1000] = 992;
        arr[991] = 10;// 重复的数是10
        print(arr);

        int[] index = demo(arr);
        System.out.println("--->"+index[0]);
        System.out.println("--->"+index[1]);
    }
}