算法：设计一个O(n)复杂度的算法，在大量数中找到前10个最大的数

一. 设计一个O(n)复杂度的算法

1、问题：计数排序

• 现在有一个列表，列表中的数范围都在0到100之间，列表长度大约为100万，设计算法在O(n)时间复杂度内将列表进行排序

2、原理

• 必须知道这些数中最大的数是多少
• 然后生成一个长度等于最大数的列表
• 循环li列表中所有的数，li中每出现一次这个数就在生成的count列表中加一
• 这样就可以在count列表中的对应位置记录出列表li中所有数出现的次数
• 然后在循环count，这个数出现几次就依次写几个到li列表中，就出现下面效果

答案：

def count_sort(li, max_num):
   count = [0 for i in range(max_num + 1)]
   for num in li:
      count[num] += 1
   i = 0
   print('count',count)
   for num,m in enumerate(count):        #循环列表count，按顺序得到li中数出现次数
      for j in range(m):            #这个数出现多少次就在li中依次追加多少个
         li[i] = num
         i += 1
li = [3,4,5,3,2,4,5,6,7,4]
count_sort(li,10)
print(li)        #[2, 3, 3, 4, 4, 4, 5, 5, 6, 7]

二. 在大量数中找到前10个最大的数

1、问题

• 现在有n个数（n>10000）,设计算法，按大小顺序得到前世大的数。
• 应用场景：榜单TOP 10

2、使用插入法解决思路（时间复杂度： O(kn)）

• 先取出待排序列表前11个元素，使用插入排序先有序
• 然后依次循环未排序的数，一个个的替换TOP 10列表中的第11号元素，再进行一次插入排序
• 这样仅循环了一次列表即可得到前11大的元素，最后列表切片，切出前10大元素即可

插入法解决：

# 一趟插入
def insert(li,i):
   tmp = li[i]      # tmp是无序区取出的一个数
   j = i - 1        # li[j]是有序区最大的那个数
   while j >= 0 and li[j] < tmp:
      #li[j] < tmp 这个条件的大于号小于号控制是10个最大的数还是最小的数
      li[j + 1] = li[j]  # 将有序区最右边的数向右移一个位置
      j = j - 1
   li[j + 1] = tmp  # 将tmp放到以前有序区最大数的位置，再依次与前一个数比较

def insert_sort(li):
   for i in range(1, len(li)):
      insert(li, i)

def topk(li,k):
   top = li[0:k+1]
   insert_sort(top)                #先将列表中的11个元素用插入法排序
   for i in range(k+1, len(li)):   #循环后面剩下的元素
      top[k] = li[i]              #依次取后面未排序的数放到top列表的最后面
      insert(top, k)              #然后再次对top进行依次排序
   return top[:-1]

li = list(range(10000))
import random
random.shuffle(li)
a = topk(li,10)
print(a)

3、使用堆排序解决思路（时间复杂度：O(nlog(k) ）

• 取列表前10个元素建立一个小根堆，堆顶就是目前的10大的数（建立小根堆）
• 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素，如果大于堆顶，则将堆顶更换为该元素，并且对堆进行依次调整
• 遍历列表所有元素后，倒序弹出堆顶

堆排序解决：

import random
def sift(data, low, high):
   '''  构造小根堆  堆定义：堆中某节点的值总是不大于或不小于父节点的值
   :param data: 传入的待排序的列表
   :param low:  需要进行排序的那个小堆的根对应的号
   :param high: 需要进行排序那个小堆最大的那个号
   :return:
   '''
   i = low            #i最开始创建堆时是最后一个有孩子的父亲对应根的号
   j = 2 * i+ 1       #j子堆左孩子对应的号
   tmp = data[i]      #tmp是子堆中原本根的值（拿出最高领导）
   while j <= high:   #只要没到子堆的最后（每次向下找一层）  #孩子在堆里
      if j + 1 <= high and data[j] > data[j + 1]: #如果有右孩纸，且比左孩子大
         j += 1
      if tmp > data[j]:       #如果孩子还比子堆原有根的值tmp大，就将孩子放到子堆的根
         data[i] = data[j]    #孩子成为子堆的根
         i = j                #孩子成为新父亲（向下再找一层）
         j = 2 * i + 1        #新孩子  （此时如果j<=high证明还有孩，继续找）
      else:
         break    #如果能干就跳出循环就会流出一个空位
   data[i] = tmp               #最高领导放到父亲位置

def topn(li,n):
   heap = li[0:n]                #先取10个元素
   for i in range(n//2 -1, -1, -1):    #使用这10个元素构建出一个小根堆
      sift(heap, i, n-1)
      #遍历
   for i in range(n, len(li)):        #依次取出剩下的元素
      if li[i] > heap[0]:            #如果新元素比堆顶元素大
         heap[0] = li[i]            #就将新元素替换堆顶元素
         sift(heap, 0, n-1)        #重新构建小根堆
   for i in range(n - 1, -1, -1):        # 上面的for循环已经找出了前十大元素，这里是排序
      heap[0], heap[i] = heap[i], heap[0]
      sift(heap, 0, i-1)
   return heap
li = list(range(1000))
import random
random.shuffle(li)
a = topn(li,10)
print(a)                                #[999, 998, 997, 996, 995, 994, 993, 992, 991, 990]

堆排找前10大元素：

# !/usr/bin/env python
# -*- coding:utf-8 -*-
import random

def sift(data, low, high):
    '''  构造小根堆 : 堆中某节点的值总是不小于父节点的值
    :param data: 传入的待排序的列表
    :param low:  需要进行排序的那个小堆的根对应的号
    :param high: 需要进行排序那个小堆最大的那个号
    :return:
    '''
    i = low                # i最开始创建堆时是最后一个有孩子的父亲对应根的号
    j = 2 * i + 1          # j子堆左孩子对应的号
    tmp = data[i]          # tmp是子堆中原本根的值（拿出最高领导）
    while j <= high:       # 只要没到子堆的最后（每次向下找一层）孩子在堆里
        if j + 1 <= high and data[j] > data[j + 1]:  # 如果有右孩纸，且比左孩子更小
            j += 1
        if tmp > data[j]:         # 如果孩子还比子堆原有根的值tmp小，就将孩子放到子堆的根
            data[i] = data[j]     # 孩子成为子堆的根
            i = j                 # 孩子成为新父亲（向下再找一层）
            j = 2 * i + 1         # 新孩子  （此时如果j<=high证明还有孩，继续找）
        else:
            break                # 如果能干就跳出循环就会流出一个空位
    data[i] = tmp                 # 最高领导放到父亲位置

def topn(li, n):
    # 1、构建10个数量的小根堆
    heap = li[0:n]                        # 先取10个元素
    for i in range(n // 2 - 1, -1, -1):   # 使用这10个元素构建出一个小根堆
        sift(heap, i, n - 1)

    # 2、找出li中前10大元素放入heap中
    for i in range(n, len(li)):          # 依次取出剩下的元素
        if li[i] > heap[0]:              # 如果新元素比堆顶元素大
            heap[0] = li[i]              # 就将新元素替换堆顶元素
            sift(heap, 0, n - 1)         # 重新构建小根堆

    # 3、利用堆排将这个小根堆倒序排列
    for i in range(n - 1, -1, -1):       # 上面的for循环已经找出了前十大元素，这里是排序
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i - 1)
    return heap

li = list(range(1000))
import random
random.shuffle(li)

print topn(li, 10)        # [999, 998, 997, 996, 995, 994, 993, 992, 991, 990]

4、使用python自带的heapq模块找到前十大元素

heapq模块解决：

import heapq
import random
heap = []
data = list(range(1000))
random.shuffle(data)
print(heapq.nlargest(10,data))
# [999, 998, 997, 996, 995, 994, 993, 992, 991, 990]

三. 其他

1、问题

• 在一个有重复数的升序列表中找到指定数的下标范围
• 例如：列表[1,2,3,4,5],若查找3，则返回（2,4）若查找1，则返回（0,0）

答案：

l = list(range(1,101))
def bin_search(data_set,val):
   low = 0
   high = len(data_set) - 1
   while low <= high:
      mid = (low+high)//2
      if data_set[mid] == val:
         left = mid
         right = mid
         while left >=0 and data_set[left] == val:
            left -= 1
         while right < len(data_set) and data_set[right] == val:
            right += 1
         return (left+1,right-1)
      elif data_set[mid] < val:
         low = mid + 1
      else:
         high = mid - 1
   return
n = bin_search(l,2)
print(n)                         # 返回1在列表中的下标范围： (1, 1)

2、在列表中找到两个数的和等于给出的数（返回找到的下标）

答案：

import copy
li = [1,2,4,3,5,]

target = 5
def bin_search(data_set,val,low,high):
   while low <= high:
      mid = (low+high)//2
      if data_set[mid] == val:
         return mid
      elif data_set[mid] < val:
         low = mid + 1
      else:
         high = mid - 1
   return

def func2():
   li2 = copy.deepcopy(li)
   li2.sort()
   for i in range(len(li2)):
      a = i
      b = bin_search(li2, target - li2[a], i+1, len(li2)-1)
      if b:
         return (li.index(li2[a]),li.index(li2[b]))
print(func2())                                             # (0, 2)

3、新建一个列表存储当前列表的下标，当前列表的值作为新下标的号

1. 原理

• 比如现在有列表 li1 = [2,1,4] ,使用这种方法必须知道li1中最大的数是多少（比如这里最大的数是：6）
• 现在新建一个列表初始值 li2 = [None,None,None,None,None]
• 使用for循环遍历li1，第一次取到li1[0]中的2，就在li2中设置li2[2] = 0
• 第二次取到的是1就在li2[1]=0
• 第三次取到的是4就在li2[4]=0
• 最后得到的li2 = [None,0,0,None,0]

2. 根据上面原理可以在列表中找到两个数的和等于给出的数（返回找到的下标）
　注：使用这种方法必须知道当前列表中的最大值

答案：

import copy
li = [1,2,4,3,5,]

target = 3
max_num = 10

def func():
   a = [None for i in range(max_num+1)]    #生成一个新列表a，列表长度是li中最大值，初始全为None
   for i in range(len(li)):
      a[li[i]] = i
      if a[target-li[i]] != None:
         return (a[li[i]], a[target-li[i]])
print(func())