Solution:
I.) Order statistics, to find the min +ve number missing from the array. Divide the array into positive and negative numbers.
Take a random no.(r) from positive array and partition the array like we do in quick sort. After partitioning the random no. is placed at the correct sorted position(k) in the array. If the left side of position 'k' contains less than k number then the missing number lies in the left half. Or else the missing number lies in the right half. Partition and continue searching.
This can search in average O(n) time, and worst case O(nlogn) time.
II.) This solution uses the indexes of the array(i) to mark the element 'i' seen by making it negative. The first index with the non negative integer is the answer.
http://www.geeksforgeeks.org/archives/19419
I.) Order statistics, to find the min +ve number missing from the array. Divide the array into positive and negative numbers.
Take a random no.(r) from positive array and partition the array like we do in quick sort. After partitioning the random no. is placed at the correct sorted position(k) in the array. If the left side of position 'k' contains less than k number then the missing number lies in the left half. Or else the missing number lies in the right half. Partition and continue searching.
This can search in average O(n) time, and worst case O(nlogn) time.
II.) This solution uses the indexes of the array(i) to mark the element 'i' seen by making it negative. The first index with the non negative integer is the answer.
http://www.geeksforgeeks.org/archives/19419
No comments:
Post a Comment