Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
This problem seems quite simple, but there's a trap: the array isn't sorted. You either need to sort it yourself (which would take at least O(n long n), so you need to use another method). Besides my method, there's also a mathematical approach: add all the numbers together and then subtract the sum of N consecutive numbers.
public class Solution { public int missingNumber(int[] nums) { int[] n = new int[nums.length+1]; for(int i=0;i This siteOriginal articleAll follow "Attribution-NonCommercial-ShareAlike 4.0 License (CC BY-NC-SA 4.0)Please retain the following annotations when sharing or adapting:
Original author:Jake Tao,source:「LeetCode – 268. Missing Number」
