首页 > 代码库 > 找轮转后的有序数组中第K小的数
找轮转后的有序数组中第K小的数
我们可以通过二分查找法,在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[r]) { 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;}
找轮转后的有序数组中第K小的数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。