Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created February 25, 2018 18:34
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jianminchen/de290a99deadac1d76f5c85c1ca6df6f to your computer and use it in GitHub Desktop.
Feb 25, 2018 - find first missing number - using in place swap - I ran into a few issues in my first writing, and then I fixed the issues based on the result of test cases.
using System;
class Solution
{
public static int GetDifferentNumber(int[] arr)
{
if(arr == null || arr.Length == 0)
return -1;
var length = arr.Length;
int index = 0;
while(index < length)
{
var current = arr[index];
var isEqual = current == index; // condition is to check value equals index value
if(!isEqual && current < length) // index-out-of-range bug in my first writing
{
swap(arr, index, current);
}
else
{
index++;
}
}
// go over the array again to find first negative number
for(int i = 0; i < length; i++)
{
if(arr[i] != i)
return i;
}
return length;
}
private static void swap(int[] arr, int start, int end)
{
var tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
}
static void Main(string[] args)
{
}
}
/*
[3, 0, 1, 4]
keyword:
unique - nonegative integers
array -
Ask: find smallest nonenative >=0 not in the array
Constraint: not allowed to modify the input arr
example: [0, 1, 2, 3], 4 - first missing number
[0, 1, 2, 100] - first missing number 3
- extra space
- bucket sort -> given the array size N, sorted[N], sort[i] = 1, i in the array,
- Look for first N number, N is the size of the array
- if nonthing is found, return N
Extra space - using the array ->
HashSet<int> -> put all the numbers,
index 0 to N - 1, go to search hashset
[0,1, 2, 3]
[0, 1, 2, 4] -> find missing 3 , size is 4
0 , 1, 2, 4 -> where is 3, 4 -> -4
[1, 0, 3, 100] -> [0, 1,-100, 3] -> if I can find any negative
[0, 1, 2, 3] -> 4
[1, 2, 3, 10] -> [2, 1, 3, 10] -> [3, 1, 2, 10]-> [10, 2, 1, 3] -> [10, 2, 1, 3] -> index
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment