Java two solutions


  • 1
    I

    By sumation. O(N) time and constant space

    public class Solution {
        public int missingNumber(int[] nums) {
    		int s = nums.length;
    		for (int i = 0; i < nums.length; i++) {
    			s += i - nums[i];
    		}
    		return s;
        }
    }
    

    By binary search. O(NlogN) time and constant space

    public class Solution {
        public int missingNumber(int[] nums) {
            int low = 0;
            int high = nums.length;
            while (low <= high) {
                int mid = (low + high) / 2;
                int c = 0;
                for (int num : nums) {
                    if (num <= mid) c++;
                }
    
                if (c == mid + 1) low = mid + 1;
                else high = mid - 1;
            }
    	    return low;
        }
    }

  • 0
    V

    if NlgN is allowed, you can sort it first


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.