草依山的Javascript世界

一个Javascript程序猿的学习纪录剩地,不仅仅是JS,还有Linux、Mac、nodeJs、吃、玩!

N个数中第K大的数

过年了看一下博客,去年产量好低,今年争取一周至少一篇吧,水的也行,嘿嘿(注意这儿只有两个嘿嘿,它是语气词,不是动词)。

我们看一下求N个数(可重复)中第K大的数怎么搞, 首先最常见的思路肯定就是先把N个数进行去重排序,我们可以用一下ES6的Set去重,然后用数组sort排序,最后取第K大的就行

下面的代码用到了一些ES6的特性,建议安装babel(npm install -g babel),然后在命令行下使用babel-node运行

或者可以在我弄的这个网页版的repl里运行代码,在控制台里看结果

function q (arry, k) {
  let uniqArry = [...new Set(arry)]
  return uniqArry.sort((a, b) => a - b)[k - 1]
}

console.log(q([1, 3, 4, 8, 12, 5], 4) === 5)
console.log(q([9, 3, 6, 1, 90], 3) === 6)
console.log(q([1, 3, 4, 8, 12, 5], 4) === 5)
console.log(q([1, 3, 4, 8, 12, 5, 4, 9, 110, 234, 355], 4) === 5)
console.log(q([31, 2, 33, 16,
    37, 8, 3, 4,
    33, 28, 17, 38,
    36, 10, 11, 13,
    4, 0, 39, 9 ], 10) === 16)

同时我在下面写了五个测试用例,运行一下返回两个true就行啦

这篇太水了,下面补上一个稍微复杂一点的解法,第二种方法同样是先利用Set去重,然后先取前k个数排序, 再把后面的m-k个数挨个处理一下,比排序后最大的数还小,那就插入到排序数组里特定的位置, 同时数组pop出一个元素,最后取排序后数组里最后一个元素就是所需要的结果。

function q (arry, k) {
  let uniqArry = [...new Set(arry)]
  let tmp = uniqArry.slice(0, k).sort((a, b) => a - b)
  let cur
  for (let i = k, len = uniqArry.length; i < len; i++) {
    cur = uniqArry[i]
    if (cur < tmp[k - 1]) { // 比最大小
      for (let m = 0; m < k; m++) {
        if (cur < tmp[m]) { // 比当前元素小,插入
          tmp.splice(m, 0, cur)
          tmp.pop()
          break
        }
      }
    }
  }

  return tmp[k - 1]
}

console.log(q([1, 3, 4, 8, 12, 5], 4) === 5)
console.log(q([9, 3, 6, 1, 90], 3) === 6)
console.log(q([1, 3, 4, 8, 12, 5], 4) === 5)
console.log(q([1, 3, 4, 8, 12, 5, 4, 9, 110, 234, 355], 4) === 5)
console.log(q([31, 2, 33, 16,
    37, 8, 3, 4,
    33, 28, 17, 38,
    36, 10, 11, 13,
    4, 0, 39, 9 ], 10) === 16)

第二种方法实质是用了分块处理,在数据量特别大的时候也许有用。

文章地址: N个数中第K大的数
欢迎关注我的微博与我交流:@草依山
Github上也有一些东西:[Github]
所有文章坚决抵制jb51.net的转载!
标签: javascript 29
2016-02-11

相关文章

2017-02-13 new做了些什么
2016-09-29 [翻译]bash的各种文件载入执行顺序
2016-05-31 phantomjs在linux下截图中文字体问题
2016-04-24 Promise的错误处理
2016-02-23 URL里的+

文章修改纪录

加载中...
Copyright © 2013. Create By 草依山, Fork