首页 > 代码库 > 选择中位数(第k大的数)
选择中位数(第k大的数)
在查找中位数时，我们可以先排序，再找中间位置的数值即可，这样时间复杂度是O(nlbn).
参考快速排序的分割算法，我们可以得到O(n)复杂度的算法。
首先,把问题推广到查找第k小的数，每次分割之后，我们只需要在pivot的一侧查找即可。
1 #define swap(a, b) do { int temp = a; a = b; b = temp; } while (0) 2 3 int partition(int A[], int left, int right) 4 { 5 int povit = left; 6 int l = left, r = right; 7 8 while (l <= r) 9 {10 while (l <= right && A[l] <= A[povit])11 l++;12 while (r >= left && A[r] > A[povit])13 r--;14 if (l < r)15 swap(A[l], A[r]);16 }17 swap(A[povit], A[r]);18 povit = r;19 return povit;20 }21 22 int select_kth(int A[], int left, int right, int k)23 {24 int povit = left;25 26 if (left == right)27 return A[povit];28 29 povit = partition(A, left, right);30 if (povit - left + 1 >= k)31 select_kth(A, left, povit, k);32 else33 select_kth(A, povit + 1, right, k - (povit - left + 1));34 }
时间复杂度： T(n) = T(n/2) + n ==>> T(n) = O(nlbn)
选择中位数(第k大的数)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。