-
有序数列第n个数
参考文档
1、用快速排序的步骤进行找，二分，但是最坏的情况是O（n^2），好的情况是O（n），平均情况是O（logk）
2.最坏的情况是每次都找到边缘的数，无法将整个序列扔掉大部分，我们要找到分开序列较好的那个数。可以在前2/3的序列中找到中点，那么这一点可以将序列分成一部分为1/3和一部分为2/3。
时间复杂度的递推式是：T(n) ≤ 2T(2n / 3) + Θ(n)，根据主方法，有时间复杂度为：O(nlog3/22)≈O(n^1.26 )
An Initial Insight
3.第三种太恶心了，看不下去。 无序数列前n个数
方法一：常规解法,先排序(时间复杂度为O(NlogN))
方法二：利用快速排序原理(时间复杂度O(N)
这里跟快速排序有所不同，快速排序平均时间复杂度为O(NlgN)，因为它需要递归调用两个部分，而寻找第K小的元素只需要考虑其中的一半。
这里的时间复杂度是平均时间复杂度？？，这个时间复杂度是怎么算出来的？？
方法三：利用最小堆的原理(时间复杂度为O(NlogK))
参考文档
2）用大小为K的数组存前K个数，然后找出这K个数中最大的数设为kmax，用时O(K)。遍历后面的N-K个数，如果有小于kmax的数，则将其替换kmax，并从新的K个数中重新选取最大的值kmax，更新用时O(K)。所以总的时间为O(NK)。
3）一个更好的方法是建堆。建立一个包含K个元素的最大堆，将后续的N-K每个数与堆顶元素比较，如果小于堆顶元素，则将其替换堆顶元素并调整堆得结构维护最大堆的性质，最后堆中包含有最小的K个元素，从而堆顶元素就是第K小的数。建堆的时间为O(K)，每次调整最大堆结构时间为O(lgK)，从而总的时间复杂度为O(K + (N-K)lgK)。
注意，堆的建立时间为O（K），如果仔细算的话，大致算是O（KlogK）。
首先维护一个n个数大小的数组，排成最小堆的结构，然后对所有数都逐一进行比较，选较大的数进来，时间复杂度为：O(K + (N-K)lgK)，若K比较小，近似O（NlogK）
方法五：用空间换取时间的方法
线性排序
快速排序算法及找到第k个数（Python）
def quicksort(data,start,last):
mid_index = partition(data,start,last)
if start < mid_index-1:
quicksort(data,start,mid_index-1)
if mid_index+1 < last:
quicksort(data,mid_index+1,last)
def partition(data,start,last):
if data is None:
return None
if start < 0 or last < 0:
return None
if last <= start:
return start
mid_num = data[start]
while start < last:
while start < last and mid_num <= data[last]:
last -= 1
data[start] = data[last]
while start < last and data[start] <= mid_num:
start += 1
data[last] = data[start]
data[start] = mid_num
return start
def main():
data = [2,4,1,3,9,8]
quicksort(data,0,len(data)-1)
print(data)
if __name__ == '__main__':
main()
Partition还可以用来查找第k个数
def find_nth_max(data,n):
if len(data) < n:
return None
n -= 1
start = 0
last = len(data)-1
mid_index = partition(data,start,last)
while mid_index != n:
if mid_index < n:
start = mid_index + 1
else:
last = mid_index - 1
mid_index = partition(data, start, last)
return data[mid_index]
