Problem
Given an integer array, find the Kth smallest number in the array.For example, given array {3, 0, -1, 0, 8, 7}, the 3rd smallest number is 0.
Solution
Solution 1:
We can sort the array with cost NlogN, then the Kth smallest number is at index K - 1.
Solution 2:
We can iterate the array 3 times, the first time, we find the smallest value.
The second time, if the current value equal to the smallest value we found last time, we ignore it, then continue to find the next smallest value.
The third time, if the current value matches any of the 2 smallest values we already saw, we ignore the position, continue to find the 3rd smallest value.
After k loops, we found the Kth smallest value. The time complexity is O(KN).
Solution 2:
We can iterate the array 3 times, the first time, we find the smallest value.
The second time, if the current value equal to the smallest value we found last time, we ignore it, then continue to find the next smallest value.
The third time, if the current value matches any of the 2 smallest values we already saw, we ignore the position, continue to find the 3rd smallest value.
After k loops, we found the Kth smallest value. The time complexity is O(KN).
Solution 3:
We can iterate the array once, find the smallest K numbers, then the largest in those K numbers are the solution. The cost is O(N).
If K = 3
we set r1 = r2 = r3 = Integer.MAX_VALUE before start traversal the array. Name current array value t.
r1 r2 r3
t
if t <= r1
r3 = r2
r2 = r1
r1 = t
else if t <= r2
r3 = r2
r2 = t
else if t <= r3
r3 = t
finally we out put r3 as the answer.
class KthSmallest {
public static void main(String[] args) {
int[] a = new int[]{3, 0, -1, 0, 8, 7};
System.out.println(getKthSmallest(a));
}
public static int getKthSmallest(int[] a) {
int N = a.length;
if(N < 2) return Integer.MAX_VALUE;
int r1 = Integer.MAX_VALUE;
int r2 = Integer.MAX_VALUE;
int r3 = Integer.MAX_VALUE;
// 3, 0, -1, 0, 8, 7
// i
// r1 r2 r3
// t
// -1 0 0
for(int i = 0; i < N; i++) {
int t = a[i];
if(t <= r1) {
r3 = r2;
r2 = r1;
r1 = a[i];
} else if(t <= r2) {
r3 = r2;
r2 = t;
} else if(t < r3) {
r3 = t;
}
}
return r3;
}
}
public static void main(String[] args) {
int[] a = new int[]{3, 0, -1, 0, 8, 7};
System.out.println(getKthSmallest(a));
}
public static int getKthSmallest(int[] a) {
int N = a.length;
if(N < 2) return Integer.MAX_VALUE;
int r1 = Integer.MAX_VALUE;
int r2 = Integer.MAX_VALUE;
int r3 = Integer.MAX_VALUE;
// 3, 0, -1, 0, 8, 7
// i
// r1 r2 r3
// t
// -1 0 0
for(int i = 0; i < N; i++) {
int t = a[i];
if(t <= r1) {
r3 = r2;
r2 = r1;
r1 = a[i];
} else if(t <= r2) {
r3 = r2;
r2 = t;
} else if(t < r3) {
r3 = t;
}
}
return r3;
}
}
The time complexity is O(N), the space complexity is O(1).
If K is a big number such as 20, this method won't be great. We need to use a stack instead. the current value t is compared with the top element in the stack. If t is smaller, the stack pop out, then the t is added to the stack in the right position. Finally, pop out the top of the stack, which is the answer.
