数组中重复的数字
数组中重复的数字
http://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524
解法一:
- 时间复杂度O(N),空间复杂度O(N)
import java.util.*; public class Solution { public int duplicate (int[] a) { int[] b = new int[a.length]; // 辅助数组,其下标代表值,数值代表出现次数 for (int i = 0; i < a.length; i++) { if (b[a[i]] == 0) b[a[i]]++; else return a[i]; } return -1; } }
解法二:
- 《剑指Offer》官方答案,就地交换,每一个数字交换不会超过2次
- 时间复杂度O(N),空间复杂度O(1)
import java.util.*; public class Solution { public int duplicate (int[] a) { for (int i = 0; i < a.length; i++) { while (a[i] != i) { if (a[i] == a[a[i]]) return a[i]; else { int tmp = a[a[i]]; a[a[i]] = a[i]; a[i] = tmp; } } } return -1; } }