找到轮转后的有序数组中第K小的数
浏览数：25 /
时间：2015年06月08日
我们可以通过二分查找法，在log(n)的时间内找到最小数的在数组中的位置，然后通过偏移来快速定位任意第K个数。
此处假设数组中没有相同的数，原排列顺序是递增排列。
在轮转后的有序数组中查找最小数的算法如下：
int findIndexOfMin(int num[],int n) {
int l = 0;
int r = n-1;
while(l <= r) {
int mid = l + (r - l) / 2;
if (num[mid] > num[size]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return l;
}接着基于此结果进行偏移，再基于数组长度对偏移后的值取模，就可以找到第K个数在数组中的位置了：
int findKthElement(int num[], int m, int k)
{
if (k > m) return -1;
int base = findIndexOfMin(num, 0, m-1);
int index = (base+k-1) % m;
return index;
}郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
