Bloomberg电面

谢谢分享！
第一题貌似可以用数学的办法求解 (1+n)*n/2 - sum

同好奇update

祝楼主好运

大家一定把这个相关系列的各种题目做好 （missing number/duplicate number），感觉好高频！好多公司在出
一个整数数列 包含1-->N  乱序，但是有一个缺失数字，让找到这个缺失数字。比如： [2,4,1,5,3,7] -> return 6. 1

楼主加油啊，感觉他家不是最优解也可能过得

第一题和follow up, 第二题还用stack就行

1. class Solution {
   
2.     public int missingNumber(int[] nums) {
   
3.         int sum = nums.length * (nums.length + 1) / 2;
   
4.         for (int num : nums) sum -= num;
   
5.         return sum;
   
6.     }
   
7. }
   
8. 
   
9. //如果是sorted的数组，在nlogn的时间做出
   
10. class Solution {
    
11.     public int missingNumber(int[] nums) {
    
12.         Arrays.sort(nums);
    
13.         if (nums[0] != 0) return 0; //只有一个元素是[0], [1]二分无法解决要提前考虑检查头尾
    
14.         if (nums[nums.length -1] != nums.length) return nums.length;
    
15.         int l = 0, r = nums.length - 1;
    
16.         while (l < r) {
    
17.             int mid = l + (r - l) / 2;
    
18.             if (nums[mid] == mid) l = mid + 1; //相等说明左边没问题找右边
    
19.             else if (nums[mid] > mid) r = mid; //element > index说明左边不对， 不会出现nums[mid] < mid，因为少一个
    
20.         }
    
21.         return l; //最后停住的地方就是缺少的
    
22.     }
    
23. }

复制代码

补充内容 (2018-9-30 06:30):
leetcode上array是 0开头的，这里改下mid+1即可

哇楼主跟我面筋好像 已被拒-=-

反射弧超长地Update一下。。。收到Onsite，但是被拒了。。。

sunx0619 发表于 2018-5-17 08:29
楼主有update吗 onsite了吗

嗯 onsite的时候被拒了