python实现求第K小
#encoding:utf-8 _author_ = "Wang Wenchao" import heapq #该包封装了最小堆,想要用最大堆则用相反数 ''' 升序数组第一个是1,后续为若干连续的素数, 对于里面的元素m和n满足m<n,都对应了一个有理数m/n, 现在给定一个数组和一个K,要求返回第K小的有理数 1 3 1 2 3 5 第一个为K 输出为 0.4 2 5 ''' n=int(raw_input()) for i in range(n): line=raw_input().split(' ') K=int(line[0]) res = [-1] *K heapq.heapify(res) left=right=0 line.pop(0) arr=[int(x) for x in line] #print arr for j in range(len(arr)-1): for h in range(j,len(arr)): dif=-float(arr[j])/arr[h] #print res if dif>min(res): left=arr[j] right=arr[h] heapq.heapreplace(res,dif) print -min(res),left,right
下面是自动计算某个范围的第K小商
#encoding:utf-8
_author_ = "Wang Wenchao"
import sys
import heapq
def FindMinK(K,arr): print arr res = [-1] *K heapq.heapify(res) left=right=0 #print arr for j in range(len(arr)-1): for h in range(j,len(arr)): dif=-float(arr[j])/arr[h] #print res print -dif if dif>min(res): print -dif,"*****" left=arr[j] right=arr[h] heapq.heapreplace(res,dif) return -min(res),left,right def IsPrim(N): k=int(pow(N,1.0/2)) for i in range(2,k+1): if N%i==0 and i!=N: return 0 return 1 def main(argv): with open('primes','w') as f: count=0 begin=int(argv[1]) end=int(argv[2]) K=int(argv[3]) for i in range(begin,end+1): if IsPrim(i)==1: print i f.write(str(i)+'\n') count+=1 print '共',count,'个质数' f.write('共'+str(count)+'个质数\n') arr=[1] with open('primes', 'r') as f: lines=f.readlines() print lines for c in range(len(lines)-1): arr.append(int(lines[c].strip())) minK,left,right=FindMinK(K,arr) print 'minK=',minK,'left=',left,'right=',right if __name__ == '__main__': #main(sys.argv) main([0,2,6,3])