There are several solutions for this question:
1. Sort and pick the k index of the array after sorted
2. Build heap and re-build it for a total of k times
3. If the max element in the array is known and acceptably large, a temp array can be used which take the value of each element in the array as the indices.
4. As below: (http://www.careercup.com/question?id=14085859)
private int FindKthSmallestItem(int[] array, int k) {
if (array == null || array.length == 0 || k > array.length || k <= 0) {
return 0;
}
int currentIndex = 1;
int KthSmallValue = array[0];
for (int i = 1; i < array.length; i++) {
if (KthSmallValue < array[i]) {
if (currentRank < k) {
KthSmallValue = array[i];
currentIndex++;
}
} else {
int MaxValue = array[i];
for (int j = 0; j < i; j++) {
if (MaxValue < array[j]
&& (currentIndex < k || KthSmallValue > array[j])) {
MaxValue = array[j];
}
}
if (MaxValue >= KthSmallValue)
currentIndex++;
KthSmallValue = MaxValue;
}
}
return KthSmallValue;
}
- will add comments later...
没有评论:
发表评论