https://leetcode.com/problems/find-all-duplicates-in-an-array/

典型的数组中的重复数。这次是通过跳转法，一个个跳转排查的。因为查过的不会重复处理，所以复杂度也是O(n)。

 

后面发现了别人一个更好的做法。。。如下：

public class Solution {    // when find a number i, flip the number at position i-1 to negative.     // if the number at position i-1 is already negative, i is the number that occurs twice.        public List
     
       findDuplicates(int[] nums) {        List
      
        res = new ArrayList<>();        for (int i = 0; i < nums.length; ++i) {            int index = Math.abs(nums[i])-1;            if (nums[index] < 0)                res.add(Math.abs(index+1));            nums[index] = -nums[index];        }        return res;    }}
      
     

 

我的做法：

package com.company;import java.util.ArrayList;import java.util.Iterator;import java.util.List;class Solution {    public List
     
       findDuplicates(int[] nums) {        List
      
        list = new ArrayList<>();        int index = 1;        while (index <= nums.length) {            int next = nums[index-1];            nums[index-1] = -1;            while (next != -1 && next != index && -1 != nums[next-1] && next != nums[next-1]) {                int tmp = nums[next-1];                nums[next-1] = next;                next = tmp;            }            if (next == -1) {            }            if (next == index) {                nums[index-1] = next;            }            else if (-1 == nums[next-1]) {                nums[next-1] = next;            }            else {                list.add(next);            }            index++;        }        return list;    }}public class Main {    public static void main(String[] args) {        System.out.println("Hello!");        Solution solution = new Solution();        int[] nums = {};        List
       
         ret = solution.findDuplicates(nums);        System.out.printf("ret len is %d\n", ret.size());        Iterator iter = ret.iterator();        while (iter.hasNext()) {            System.out.printf("%d,", iter.next());        }        System.out.println();    }}