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<Integer> findDuplicates(int[] nums) {
List<Integer> 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<Integer> findDuplicates(int[] nums) {
List<Integer> 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<Integer> 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(); }
}