Coding Interview Questions: No. 37 - Missing Number in an Array
Problem 2: An sorted array n - 1 unique numbers in the range from 0 to n - 1. There is only one number in the range from 0 to n - 1 missing. Please write a function to find the missing number.Analysis: Of couse, we could use the solution above to solve this problem, which costs O(n) time. This solution does not utilize the properties of sorted arrays.
Since numbers from 0 to n - 1 are sorted in an array, the first numbers should be same as their indexes. That's to say, the number 0 is located at the cell with index 0, the number 1 is located at the cell with index 1, and so on. If the missing number is denoted as m. Numbers less then m are located at cells with indexes same as values.
Read full article from Coding Interview Questions: No. 37 - Missing Number in an Array
No comments:
Post a Comment