算法题目7：从若干数据里取前N个最大的值

题目：有一亿多个值，去最大的一万个值，要求时间复杂度最小

实现：

// topk find the top k elements of nums
function topk(nums, k){
  if(nums.length <= k) {
    nums.sort((a,b)=>b-a);
    return nums;
  }
  
  let top = nums.slice(0,k);
  top.sort((a,b)=>b-a);
  for (let n of nums.slice(k)) {
    // search n's index in top
    let idx = binary_search(top, n);
    if (idx>=k) continue;
    // move numbers after idx backwards and drop the last one
    for (let j = top.length-1; j > idx; j--) {
      top[j] = top[j-1];
    }
    // insert n
    top[idx] = n;
  }
  return top;
}
// binary_search search num's insert position
function binary_search(sorted_nums, num) {
  let m = 0;
  let n = sorted_nums.length-1;
  while (m<=n) {
    let k = Math.floor((m+n)/2);
    
    if (num <= sorted_nums[k]) {
      m = k+1;
    } else {
      n = k-1;
    }
    
  }
  return m;
}

function createNums(N) {
    let nums = [];
    for (let i =0; i < N; i++) {
        let r = Math.floor(Math.random()*1000)
        nums.push(r)
    }
    console.log(nums)
    return nums
}

topk(createNums(20), 6)

单元测试：

function unit_test() {
    const N = 20;
    let nums = [];
    let sorted_nums = [];
    for (let i =0; i < N; i++) {
        let r = Math.floor(Math.random()*1000)
        nums.push(r)
        sorted_nums.push(r)
    }
    sorted_nums.sort((a,b)=>b-a)
    
    
    // test 100 times
    let errors = 0;
    let success = 0;
    let total = 100;
    for (let i = 0; i < total; i++ ) {
        
        let k = Math.floor(Math.random()*N)
        let top = topk(nums,k)
        if (top.toString() != sorted_nums.slice(0,k).toString()) {
            errors++
        }else {
            success++
        }
    }
    
    console.log("have", total, "case,", success, "success,", errors, "errors")
}
unit_test()