找出数组中第 k 大的数字及其出现次数
栏目: JavaScript · 发布时间: 5年前
内容简介:这是前端面试过程中遇到的一道算法题,虽说难度不大,但是也有些细节的地方需要仔细考虑。比如说数组 [1, 2, 4, 4, 3, 5],第 2 大的数字是 4,出现了 2 次。下面以这个为例展开算法的讲解。先说说大体的思路,然后再考虑一些细节性的问题。
这是前端面试过程中遇到的一道算法题,虽说难度不大,但是也有些细节的地方需要仔细考虑。
比如说数组 [1, 2, 4, 4, 3, 5],第 2 大的数字是 4,出现了 2 次。下面以这个为例展开算法的讲解。
先说说大体的思路,然后再考虑一些细节性的问题。
-
既然涉及到数字大小的问题,那就要对给定数组进行排序,题目要求“第 k 大”的数字,故选择降序的方式更有利于后面的查找;
-
重点来了,需要遍历数组,对当前遍历到的数组元素的大小排名和 k 值进行比较,若排名大于 k 值则结束循环;如果排名等于 k 值,则将该数组元素记为第 k 大的数字,且次数加一;
-
那如何确定遍历的当前数组元素的大小排名呢?我们先将数组的第一项定为第 1 大的数字,然后比较第一项和第二项是否相等,若相等则第二项也为第 1 大;如果不相等则数组第二项为第 2 大的数字。依次类推,可获知每次遍历的数组元素的大小排名。
整体的思路讲完了,现在看看细节性的东西——边界判断
-
给定的 k 值是否大于或等于 1(保证没有第 0 大的数字),且 k 值小于或等于数组的长度(因为数组经降序 排序 后,值最小的数组元素的大小排名值不可能比数组长度值更大)。这条判断隐含了数组不能为空的条件。
-
遍历结束时,k 值不能超出值最小的数组元素的大小排名,若超出了,说明数组中不存在这样的数字。
根据以上思路和细节考虑写出的算法如下:
function findKthNum (arr, k) { var len = arr.length; // 对给定的 k 值进行判断,确保 len >= k >= 1 if (k > len || k < 1) { console.log("There doesn't exists the number you want !"); return; } // 获得数组的副本 var _arr = arr.slice(); // 遍历数组时,当前数组元素的大小排名 var rank = 1; // 第 k 大的数字 var num = 0; // 第 k 大数字的出现次数 var count = 0; // 对 _arr 进行降序排序 _arr.sort(function (a, b) { return b - a; }); for (var i = 0; i < len; i++) { var j = i + 1; // 对当前数组元素的大小排名和 k 值进行比较,若排名大 // 于 k 值则结束循环;如果排名等于 k 值,则将该数组 // 元素记为第 k 大的数字,且次数加一。 if (rank > k) { break; } else if (rank == k) { num = _arr[i]; count++; } // 若当前遍历的数组项与下一项数字不相等,则说明下一个 // 数字的排名值比当前遍历数字的排名刚好大 1 if ((j < len) && (_arr[i] != _arr[j])) { rank++; } } // 遍历结束时,若最后遍历的数组元素的大小排名小于给定的 k 值,则说 // 明数组中没有第 k 大的数字,即 k 值超出了所有数组元素的大小排名。 if (rank < k) { console.log("There doesn't exists the number you want !"); } else { console.log('第' + k + '大的数字:' + num, '出现次数:' + count); } } 复制代码
最后给出一些测试用例:
// 正常情况,findKthNum(arr1, 2) var arr1 = [1, 2, 4, 4, 3, 5]; // 数组为空,findKthNum(arr2, 2) var arr2 = []; // k 值小于 1,findKthNum(arr3, 0) var arr3 = [1, 2, 4, 4, 3, 5]; // k 值大于数组长度,findKthNum(arr4, 7) var arr4 = [1, 2, 4, 4, 3, 5]; // k 值超出了所有数组元素的大小排名,findKthNum(arr5, 6) var arr5 = [1, 2, 4, 4, 3, 5]; 复制代码
以上所述就是小编给大家介绍的《找出数组中第 k 大的数字及其出现次数》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 找出数组中出现次数超过一半的数
- 算法 - 找出数组中子集乘积的最大值
- 改进,从一个数组中找出 N 个数,其和为 M 的所有可能
- 从一个数组中找出 N 个数,其和为 M 的所有可能--最 nice 的解法
- 用堆找出最小的 N 个数
- MySQL如何找出未提交事务信息
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
编程珠玑(第2版•修订版)
[美] Jon Bentley 乔恩•本特利 / 黄倩、钱丽艳 / 人民邮电出版社 / 2014-12 / 39
历史上最伟大的计算机科学著作之一 融深邃思想、实战技术与趣味轶事于一炉的奇书 带你真正领略计算机科学之美 多年以来,当程序员们推选出最心爱的计算机图书时,《编程珠玑》总是位于前列。正如自然界里珍珠出自细沙对牡蛎的磨砺,计算机科学大师Jon Bentley以其独有的洞察力和创造力,从磨砺程序员的实际问题中凝结出一篇篇不朽的编程“珠玑”,成为世界计算机界名刊《ACM通讯》历史上最受欢......一起来看看 《编程珠玑(第2版•修订版)》 这本书的介绍吧!