【java版】如何找到缺失的QQ号码？

缺失的QQ号码？"/>

【java版】如何找到缺失的QQ号码？

今天涛哥更新了一篇（腾讯三面：缺失的QQ号码是哪个？），看到标题挺感兴趣的。只是我对C不了解，照着代码改了一版java的。改的时候也学着吃透涛哥讲的原理，也算是一种学习吧。

腾讯三面：缺失的QQ号码是哪个？腾讯面试题，刷起来。

模仿涛哥（三. 巧妙标记）这一算法写的java代码，代码如下：

/*** * @author JinL*参考哈希算法，并在标记元素是否存在时做巧妙优化**/public class Main {public static void main(String[] args) {int[] a = new int[] { 3, 4, 1, -1 };Main s = new Main();System.out.println(s.solution(a));}public int abs(int x) {if (x < 0) {return -x;} else {return x;}}public int solution(int[] a) {int n = a.length;for (int i = 0; i < n; i++) {/*** 假设a中的n个元素占满了1~n, 那么缺失的最小正整数就是n+1。 假设a中的n个元素没有完全占满1~n, 那么缺失的最小正整数必然是1~n之间的某个数。* 根据如上述的两句话句话，可以看出a[i]如果小于0，那必然占不满1~n,所以最小正整数肯定不是n+1。此时将a[i]赋值为n+1,也是将结果排除为n+1。*/if (a[i] <= 0) {a[i] = n + 1;}}for (int i = 0; i < n; i++) {int num = abs(a[i]);if (num <= n) {a[num - 1] = -abs(a[num - 1]);}}for (int i : a) {
//			System.out.println("a:" + i);}for (int i = 0; i < n; i++) {if (a[i] > 0) {return i + 1;}}return n + 1;}}