我的技术博客|有一个100万的数组，里边有两个是重复的，如何设计算法找到我的技术博客|java

输出：两个重复的元素的索引
【我的技术博客|有一个100万的数组，里边有两个是重复的，如何设计算法找到】

首先，直接两重循环查找不是不行，估计是最蠢的做法了。
其次，先用快速排序拍一遍，然后遍历，时间复杂度最好的情况是最坏的情况是nlogn+n
有人说是用hash，有人说用位图，不知道什么情况，用起来估计很麻烦。
其实最好想的一个方式为HashSet方式，在数量不那么大的情况下没问题的，100万同时加载到内存中可以接受，主要考虑时间复杂度。
代码如下：

int a[] = { 6, 4, 18, 10, 24, 8, 9, 16, 19, 13, 25, 15, 12, 11, 2, 0, 14, 17, 12, 5 }; int n = a.length; Set intSet = new HashSet(); for (int i = 0; i < n; i++) { if (!intSet.add(a[i])) { System.out.println(a[i]); break; } }

这里只把第二重复的元素打印出来了，如果还需要找前一个，就需要更多的操作了，比如HashSet中存储一个对象，同时包含index/value，找到重复的value之后，通过遍历比较value获取index。这里需要多加一个遍历的过程。模拟HashMap的实现过程，下了如下代码：

public void testFindRepeatInt2() { int a[] = { 6, 4, 18, 10, 24, 8, 9, 16, 19, 13, 25, 15, 12, 11, 2, 0, 14, 17, 12, 5 }; int n = a.length; IndexValue iv[] = new IndexValue[n]; IndexValue target = null; for (int i = 0; i < n; i++) { if (null != (target = put(a, i, iv))) { System.out.println("第一个数：a【" + target.index + "】==" + target.value); System.out.println("第二个数：a【" + i + "】==" + a[i]); break; } }System.out.println(Arrays.toString(iv)); } private IndexValue put(int[] a, int i, IndexValue[] iv) { int index = a[i] % iv.length; IndexValue target = null; if (iv[index] == null) { iv[index] = new IndexValue(i, a[i]); } else { IndexValue temp = iv[index]; if (null != (target = contains(temp, a[i]))) { return target; } else { IndexValue newIv = new IndexValue(i, a[i]); newIv.next = temp; iv[index] = newIv; } } return target; } private IndexValue contains(IndexValue temp, int value) { if (temp.value =https://www.it610.com/article/= value) { return temp; } if (temp.next != null) { return contains(temp.next, value); }return null; } class IndexValue { int index; int value; IndexValue next; public IndexValue(int index, int value) { super(); this.index = index; this.value = value; }@Override public String toString() { return"IndexValue [index=" + index + ", value="https://www.it610.com/article/+ value +", next=" + next + "]"; } }

由于这里的元素都是int 类型的，在进行数据散列的时候，这里为了图方便，没有取hashCode，如果是String或者其他类型可以使用HashCode进行散列。如果HashCode散列的比较好，最好的情况下，不需要进行链表操作，那么整个算法的时间复杂度就是O（n），最坏的情况下是HashCode完全没有散列开，时间复杂度为O(n^2)
当然这里使用HashMap方式来实现也是可以的，value作为key，index作为value，通过containsKey方法判断当前是否已存在该key，如果已存在直接取出来就达到目的了。
如果非要自己找点事情做的话，还是通过Hash的思路来：
假设每一个元素数组中都是散裂开的，没有重复的，那么这时候的时间复杂度岂不是最高？问题在于如何保证HashCode绝对不重复。
未完待续……