本文共 772 字，大约阅读时间需要 2 分钟。

题目：

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

示例：

输入:[4,3,2,7,8,2,3,1]输出:[2,3]

解题思想： 题目有一个重要条件1<a[i]<n,这个条件我们可以得到如果a[i]这个数出现两次，则一次循环中第a[i]个数我就可以遍历两次。

如图，图中两次遍历到第4个数，即a[4-1],即a[3]。

通过这个思路，

我们可以在第一次遍历到第a[i]个数的时候，

即a[a[i]-1]的时候让这个数为负值，

如果a[i]出现两次，那么第二次出现的时候a[a[i]-1]就会为负，

这时将a[i]添加进集合就行。

但这样做还是不对的，因为如图如果图中的2后面还会出现，

就将2忽略了因为不存在a[-2-1],即a[-3]

所以还要小小的改善，改成a[Math.abs(a[i])-1],即a[|-2|-1]

就ok了

package com.hyh.java_algorithm;import java.util.ArrayList;import java.util.List;public class FindDuplicates {    public static List
   
     findDuplicates(int[] nums){        List
    
      rs = new ArrayList();        for(int i=0;i
     
       duplicates = findDuplicates(nums);        System.out.println(duplicates);    }}
     
    
   

转载地址：http://dyfrn.baihongyu.com/