找出第k大的数 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

#7 找出数组中第k小的数

「HW面试题」【题目】给定一个整数数组，如何快速地求出该数组中第k小的数。...假如数组为[4,0,1,0,2,3]，那么第三小的元素是1 【题目分析】这道题涉及整数列表排序问题，直接使用sort方法按照ASCII码排序即可【解答】 1 #!...coding: utf-8 -*- 3 4 5 num = [4, 0, 1, 0, 2, 3] 6 num.sort() # 按照ASCII码排序 7 print(num[(3-1)]) # 第k...小的元素对应于列表索引为k-1 程序源代码

6921 0

数组中第 K 大的数

从快排的核心操作中可以看到，如果分界值的位置刚好是 K（升序为从后往前数），那么该分界值为数组中第 K 大的数。如果分界值的位置小于 K，则继续在右子数组中按照相同的方式寻找，反之在左子数组中寻找。...5.实现示例 5.1 C++ // findKthLargest 寻找数组中第 K 大的数。...K 大的数。...K 大的数。...K 大的数。

1.1K1 0

您找到你想要的搜索结果了吗？

是的

没有找到

找出数组中的第 K 大整数（排序）

题目给你一个字符串数组 nums 和一个整数 k 。 nums 中的每个字符串都表示一个不含前导零的整数。返回 nums 中表示第 k 大整数的字符串。...注意：重复的数字在统计时会视为不同元素考虑。例如，如果 nums 是 [“1”,“2”,“2”]，那么 “2” 是最大的整数，“2” 是第二大的整数，“1” 是第三大的整数。...示例 1：输入：nums = ["3","6","7","10"], k = 4 输出："3" 解释： nums 中的数字按非递减顺序排列为 ["3","6","7","10"] 其中第 4 大整数是..."3" 示例 2：输入：nums = ["2","21","12","1"], k = 3 输出："2" 解释： nums 中的数字按非递减顺序排列为 ["1","2","12","21"] 其中第...3 大整数是 "2" 示例 3：输入：nums = ["0","0"], k = 2 输出："0" 解释： nums 中的数字按非递减顺序排列为 ["0","0"] 其中第 2 大整数是 "0"

8543 0

golang刷leetcode 找出第k小

给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。...示例 1: 输入： nums = [1,3,1] k = 1 输出：0 解释：所有数对如下： (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 因此第 1 个最小距离的数对是 (1,1...)，它们之间的距离为 0。...对于第k小（大）的问题首先想到的是堆，对于第k小用大根堆。...3，删除元素，每次都是取出堆顶元素，然后将数组末尾元素放到堆顶，如果堆顶新元素小于任何一个孩子，则与孩子中交大者交换，直到叶子节点 4，对于本题，可以设置大小为k的大顶堆，当堆未满进行2，3步，如果堆满

2874 0

找出第 K 大的异或坐标值（DP）

请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。...示例 2：输入：matrix = [[5,2],[1,6]], k = 2 输出：5 解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。...示例 3：输入：matrix = [[5,2],[1,6]], k = 3 输出：4 解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。...示例 4：输入：matrix = [[5,2],[1,6]], k = 4 输出：0 解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。...取第K大的值，偷懒直接排序做，时间复杂度 O (

4491 0

如何在 10 亿数中找出前 1000 大的数

之前小史在 BAT 三家的面试中已经挂了两家，今天小史去了 BAT 中的最后一家面试了。简单的自我介绍后，面试官给了小史一个问题。 ? 【面试现场】 ?...题目：如何在 10 亿数中找出前 1000 大的数？ ? ? ? ? ? ? ? 小史：我可以用分治法，这有点类似快排中 partition 的操作。...随机选一个数 t，然后对整个数组进行 partition ，会得到两部分，前一部分的数都大于 t ，后一部分的数都小于 t 。 ? ?...如果前一部分的数小于 1000 个，那就在后一部分再进行 partition ，寻找剩下的数。 ? ? ? ? ? 小史：首先，partition 的过程，时间是 o(n)。...buildHeap(n, data); // n往后的数进行调整 for(int i = n; i < data.length; i++) {

6092 0

数组中第K小的数

简介查找一个序列中的最大/最小值时间复杂度均为，而查询一个序列中第大的数时间复杂度最坏情况下即为排序的最好时间复杂度只考虑比较排序），但利用快排的思想也可以达到期望的时间复杂度...然后判断：如果枢轴左边小于等于枢轴的序列大小等于，则说明第小的数即为枢轴。如果枢轴左边小于等于枢轴的序列大小大于，则说明第小的数一定在枢轴左边的序列。...{ return FindKth(mid+1,t,k+(s-mid)-1,cmp); } } // 查找第 k 大的数（随机化版本） template ...} else { return FindKth(gt+1,t,k-(gt-s+1),cmp); } } // 查找第 k 大的数（随机化版本） template <typename...} else { return FindKth(gt+1,t,k-(gt-s+1),cmp); } } // 查找第 k 大的数（随机化版本） template <typename

1.1K2 0

找出链表中倒数第K个节点

今天来看一道有意思的链表算法题目。给到一个单向链表，要求找出该链表中倒数第 k 个节点，要求只能遍历一次链表，且空间复杂度为 O(1)。...思路1：如果能从链表尾部开始遍历，那只需倒序遍历 k 个节点即是要找出的节点，但是由于是单链表，只能从头结点开始遍历。...思路2：先遍历一遍该单链表，获取链表的总节点数 n，那么第 n-k+1 这个节点就是倒数第 k 个节点。所以第二次再遍历到第 n-k+1 这个节点即可，但是题目要求只能遍历一遍链表。...这样前后两指针的距离始终都保持为 k-1，当前指针遍历到链表的最后一个节点时，后指针刚好也就到了倒数第 k 个节点了。如果还没想明白的话，看下面的图应该就很好理解了。...推荐文章： mysql索引为啥要选择B+树 (下) 找出数组中只出现一次的数

6912 0

找出第 K 大的异或坐标值

请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。...示例 1：输入：matrix = [[5,2],[1,6]], k = 1 输出：7 解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。...示例 2：输入：matrix = [[5,2],[1,6]], k = 2 输出：5 解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。...题解：二维差分+最小堆前缀和模板+维护k个元素的最小堆 class Solution { public: int prefix[1000][1000]; int kthLargestValue...可以看到问题可以转换为查找最后一个小于等于target的数。因为当查找到大于等于target时要往上不断压缩区间，直到小于等于k为止。

4036 0

【面试必备】如何在10亿数中找出前1000大的数?

简单的自我介绍后，面试官给了小史一个问题。【面试现场】题目：如何在10亿数中找出前1000大的数？小史：我可以用分治法，这有点类似快排中partition的操作。...随机选一个数t，然后对整个数组进行partition，会得到两部分，前一部分的数都大于t，后一部分的数都小于t。小史：如果说前一部分总数大于1000个，那就继续在前一部分进行partition寻找。...如果前一部分的数小于1000个，那就在后一部分再进行partition，寻找剩下的数。小史：首先，partition的过程，时间是o(n)。...而n+n/2+n/4+...显然是小于2n的，所以这个方法的渐进时间只有o(n) （注：这里的时间复杂度计算只是简化计算版，真正严谨的数学证明可以参考算法导论相关分析。）半分钟过去了。...小史：感悟还挺深的。虽然平时做过topN的问题，知道分治法时间更少。但是碰到具体问题的时候还是要具体分析，这种大数据量的情况下反而用堆会更快。 ?

8163 0

【面试现场】如何在10亿数中找出前1000大的数

简单的自我介绍后，面试官给了小史一个问题。 ? 【面试现场】 ? 题目：如何在10亿数中找出前1000大的数？ ? ? ? ? ? ? ?...小史：我可以用分治法，这有点类似快排中partition的操作。随机选一个数t，然后对整个数组进行partition，会得到两部分，前一部分的数都大于t，后一部分的数都小于t。...如果前一部分的数小于1000个，那就在后一部分再进行partition，寻找剩下的数。 ? ? ? ? ? 小史：首先，partition的过程，时间是o(n)。...而n+n/2+n/4+...显然是小于2n的，所以这个方法的渐进时间只有o(n) ? （注：这里的时间复杂度计算只是简化计算版，真正严谨的数学证明可以参考算法导论相关分析。） ? ? ?...buildHeap(n, data); // n往后的数进行调整 for(int i = n; i < data.length; i++) {

4011 0

7617:输出前k大的数

7617:输出前k大的数查看提交统计提问总时间限制:10000ms单个测试点时间限制:1000ms内存限制:65536kB描述给定一个数组，统计前k大的数并且把这k个数从大到小输出。...输入第一行包含一个整数n，表示数组的大小。n < 100000。第二行包含n个整数，表示数组的元素，整数之间以一个空格分开。每个整数的绝对值不超过100000000。第三行包含一个整数k。...k 大到小输出前k大的数，每个数一行。

9955 0

Day6-线性表-堆-数组中第K大的数

二直接上题 Q：已知一个未排序的数组，求数组中第K大的数如：array = 【3，2，1，5，6，4】，k = 2，那么结果就是5 三完整代码及运行结果冷静分析：如果你这时候对面试官说...，把数组排序，再倒着取第k个不就行了，那你一定没考虑到，排序后数组中的数依然可能有重复，这种情况。...所以记住就好：关于第k大，第k小的，前k个，等等，这种问题，甭想，面试官一定想问你的是，堆。...2的，最小堆，[5，6] 堆顶元素5，即为第2大的数???...less_heap.push(nums[i]); } } return less_heap.top();//堆顶即为第K大的数 } int main(){ vector

6922 0

【BAT面试必会】如何在10亿数中找出前1000大的数

【面试现场】题目：如何在10亿数中找出前1000大的数？ ? ? ? ? ? ? ? 小史：我可以用分治法，这有点类似快排中partition的操作。...随机选一个数t，然后对整个数组进行partition，会得到两部分，前一部分的数都大于t，后一部分的数都小于t。 ? ?...如果前一部分的数小于1000个，那就在后一部分再进行partition，寻找剩下的数。 ? ? ? ? ? 小史：首先，partition的过程，时间是o(n)。...而n+n/2+n/4+...显然是小于2n的，所以这个方法的渐进时间只有o(n) ? （注：这里的时间复杂度计算只是简化计算版，真正严谨的数学证明可以参考算法导论相关分析。） ? ? ?...buildHeap(n, data); // n往后的数进行调整 for(int i = n; i < data.length; i++) {

5371 0

leetcode链表之找出倒数第k个节点

序本文主要记录一下leetcode链表之找出倒数第k个节点题目输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。...例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。...= null && k > 0) { c1 = c1.next; k--; } ListNode c2 = head;...，然后两个指针同步走，当快指针走到头时，慢指针就是链表倒数第k个节点。...小结这里采用了快慢指针的套路，先让快指针走k步，然后两个指针同步走，当快指针走到头时，慢指针就是链表倒数第k个节点。

3803 0

leetcode链表之找出倒数第k个节点

序本文主要记录一下leetcode链表之找出倒数第k个节点 136_0.png 题目输入一个链表，输出该链表中倒数第k个节点。...为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。...这个链表的倒数第3个节点是值为4的节点。示例：给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5. ...，然后两个指针同步走，当快指针走到头时，慢指针就是链表倒数第k个节点。...小结这里采用了快慢指针的套路，先让快指针走k步，然后两个指针同步走，当快指针走到头时，慢指针就是链表倒数第k个节点。

8731 0

找出100以内的孪生数

1 问题两个素数之差为2的数称为“孪生数”，那么如何利用python求出100以内的所有素数呢？ 2 方法先用两次for循环求出100内的所有素数。再用while循环求出它们之间的差为2....second-first==2: print(f'{first}和{second}之间是孪生素数') index+=1 3 结语针对此类求素数问题，提出for循环和while循环的方法...，通过以上实验，证明该方法是有效的，本文的仍有方法不足或考虑不周的地方，未来可以继续研究更加高级简便的方法。

1901 0

乘法表中第k小的数

但是你能在乘法表中快速找到第k小的数字吗？给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。...例 1：输入: m = 3, n = 3, k = 5 输出: 3 解释: 乘法表: 1 2 3 2 4 6 3 6 9 第5小的数字是 3 (1, 2, 2...例 2：输入: m = 2, n = 3, k = 6 输出: 6 解释: 乘法表: 1 2 3 2 4 6 第6小的数字是 6 (1, 2, 2, 3, 4, 6)....对于该问题假设我们已经知道了一个数记做target，target的上界为m * n,下界为1，只需统计乘法表中不大于target元素的数目与k相比即可。...int left = 1; // 找到满足条件的最小的这是由于某个乘法表中不存在的数亦会使得count = k while(left < right){

1.1K2 0

第K个最大的数+优化优先队列

第K个最大的数给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。...看看源码 private final static int max= 10^5 +1; //优先队列PQ //给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。...，把减少的部分尽量换成时间复杂度为O(1)的比较操作，这样假设有m次add，那么有（n-m）次比较，综合起来就是O(klogk）+O(n-k）题目中要求第K个最大的数，数组长度是N，所以定义堆的时候大小为...K，然后用剩下的N-k个数和堆顶元素比较，最后堆顶即为结果：（1）如果K>2/N,最好做（N-K）次add操作。...第K个最大的数，就是第（N-K）个最小的数，因此用（N-K）大小的最大堆，堆顶就是结果。

1671 0

如何在大量数据中找出第2大的数字

如何在大量数据中找出第2大的数字?...了解topN解决方式的一定知道这种情况二叉查找树是一个最优选择; 针对相同数字的问题,最合适的去重数据结构就Set. 最终符合这两种条件的数据结构就是TreeSet....super K> comparator) { this.comparator = comparator; } 通过观察put方法,可以通过比较器,自定义规则,放新插入的值放入合适的位置 fixAfterInsertion...(e)方法会对树(实际是红黑树)进行旋转维护. public V put(K key, V value) { EntryK,V> t = root; ......EntryK,V> e = new Entry(key, value, parent); fixAfterInsertion(e); ... }

8951 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭