建设工程有限公司企业网站_网上国网推广经验_有什么好的网站吗_在百度做广告多少钱

1.题目： 

 

 

2.解析：
方法一：用哈希表：记录存在的数字，找到哈希表为空的数字输出

Set<Integer> set = new HashSet<>();for(int x : records) set.add(x);for(int i = 0; i < set.size(); i++){if(!set.contains(i)) return i;}return set.size();

---

方法二：位运算异或 

int ret = 0;for (int i = 0; i < records.length; i++) {ret ^= records[i];ret ^= i + 1;}return ret;

---

方法三：直接遍历

int ret = 0;for(int i = 0; i < records.length; i++){if(records[i] != i) return i;}return records.length;

---

方法四：二分查找： 

注意：特殊情况整个数组元素及对应下标都一样时

 

int left = 0,right = records.length-1;while(left < right){int mid = left + (right - left) / 2;if(records[mid] == mid) left = mid+1;else right = mid;}//特殊情况：整个数组元素及对应下标都一样时return records[left] == left ? left+1 : left;