Created
December 3, 2017 20:54
-
-
Save jianminchen/83b6bf9d1e9c14f5f4767b873b99e5a0 to your computer and use it in GitHub Desktop.
Find missing number - 30 minutes practice
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
class Solution | |
{ | |
public static int GetDifferentNumber(int[] arr) // [0, 1, 2, 3], [100,2, 0, 300] | |
{ | |
if(arr == null || arr.Length == 0) // false | |
{ | |
return 0; | |
} | |
var length = arr.Length; // 4 | |
var visited = new int[length]; | |
var foundBiggerThanN = false; | |
for(int index = 0; index < length; index++) | |
{ | |
var visit = arr[index]; // 0, 1 //100 | |
var foundBigger = visit >= length; // false, false // true | |
if(foundBigger) | |
{ | |
foundBiggerThanN = true; // true | |
} | |
else // out-of-range | |
{ | |
visited[visit] = 1; // visited[0] = 1, | |
} | |
} | |
if(!foundBiggerThanN) // true, false | |
{ | |
return length; // 4 | |
} | |
var missing = 0; // visited[0] = 1, visited[1] = 0, visited[2] = 1 visited[3]=0 | |
for(int index = 0; index < length; index++) | |
{ | |
if(visited[index] == 0) | |
{ | |
missing = index; | |
break; // bug -> | |
} | |
} | |
return missing; | |
} | |
static void Main(string[] args) | |
{ | |
} | |
} | |
// [0, 1, 2, 3], answer 4 , nonnegative >= 0, smallest not in the array | |
// array size n, | |
// 0 - n -1, each number is in the array, the answer n, | |
// unique -> any number >= n, the answer should be < n | |
// array - hashset 0 - n-1, index = 0 | |
// recodingArray[index] = 1 -> linear scan O(1) | |
// max > n true -> n | |
// max > n true | |
// = 0 O(n) first one is zero | |
// O(n), space complexity O(n) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment