>

自由软件精神——“自由、开放、分享”。自由软件自诞生之日起,就秉承了学术自由的思想,信奉科学无国界,知识应该全人类共享。

ubuntu精神——人道待人,天下共享连接人人的信念。具有 ubuntu 精神的人心胸开阔,乐于助人,见贤思齐而不忌妒贤能......

Top K problem

__author__ = 'bone-lee'

def partition(arr,low,high):
    assert low<=high
    pivot=arr[low]
    i,j=low+1,high
    while True:
        while i<high and arr[i]<=pivot: i+=1
        while j>=low and arr[j]>pivot: j-=1
        if i<j:
            arr[i],arr[j]=arr[j],arr[i]
            i+=1
            j-=1
        else:
            break
    arr[low],arr[j]=arr[j],arr[low]
    return j

def top_k(arr,k):
    length=len(arr)
    assert length>0 and 0<k<length
    low,high=0,length-1
    index=partition(arr,low,high)
    while index!=(k-1):
        if index>(k-1):
            high=index-1
            index=partition(arr,low,high)
        else:
            low=index+1
            index=partition(arr,low,high)
    return arr[:k]

def test_top_k():
    from random import randint
    # test argument
    test_times=1000
    num_start,num_end=0,100
    arr_len=50
    k=10
    for i in range(test_times):
        arr=[randint(num_start,num_end) for i in range(arr_len)]
        copied_arr=list(arr)
        k_arr=top_k(arr,k)
        copied_arr.sort()
        k_arr.sort()
        assert copied_arr[:k]==k_arr
    print "test OK"

if __name__=='__main__':
    test_top_k()

Meta

发布: 十二月 1, 2014

作者: Bone Lee 李智华

评论:  

字数统计: 134

下一篇: leetcode刷题 Reverse Nodes in k-Group

上一篇: 随机数产生

Bookmark and Share

Tags

interview python test

comments powered by Disqus

返回顶部