首页 > 其他分享 >《剑指Offer》-40-最小的 K 个数

《剑指Offer》-40-最小的 K 个数

时间:2023-08-19 20:33:08浏览次数:42  
标签:index arr end Offer int 个数 40 start small

如果直接调用 sort API 然后要几个打印几个就没意思了,应该是和某个排序的内部过程结合
首先排除O(N2)的低效率排序算法,最先想到的其实是堆排序,小根堆,但是需要额外的空间
其次像快排、归并这样的也不合适……
我想到了可以这样,快排第一轮划分之后,将部分舍去……
应该就是这样了,堆排序或者快排

思路

4,5,1,6,2,7,3,8

快排

首先选择 4 作为第一个基准,大的放右边,小的放左边,最后我们可以得到 4 在整个排序序列中的索引位置,它是第 4 小的数字,正好满足目标,于是舍去右边一边,对剩下的继续进行快排

那么如果没这么巧合,要求的大于或者小于目标怎么办?

比如 k = 3,

快排是原地排序算法,但是题目要求返回一个数组

第一次 AC 代码

	vector<int> getLeastNumbers(vector<int>& arr, int k) {
		int len = arr.size();
		if (len == 0)return {};
		QuickSort(arr, 0, len - 1, k);
		vector<int> res(k);// 准备长度为k的数组用于返回
		copy(arr.begin(), arr.begin() + k, res.begin());
		return res;
	}

	void QuickSort(vector<int>& arr, int start, int end, int k) {
		int index = Paritition(arr, start, end);
		// 如果index>k,那么大于index那一部分就不需要再处理了
		// 所以只需要排index<=k的部分
		if (start < index) QuickSort(arr, start, index - 1, k);
		if (index < (k - 1) && index < end)QuickSort(arr, index + 1, end, k);
	}

	int RandomInRange(int start, int end) {
		srand(time(nullptr));
		return rand() % (end - start + 1) + start;
	}

	// 划分函数会返回每一次划分得到的基准的索引
	int Paritition(vector<int>& arr, int start, int end) {
		int index = RandomInRange(start, end);
		swap(arr[index], arr[end]);// 既然基准是随便选的,这里能不能就直接选arr[end],这样还不用交换了
		int small = start - 1;// small指向最后一个比基准小的元素,所以对于比基准大的元素small指针不会移动
		// 服用index,因为之前index代表的索引没有意义,对应的数字我们也知道就是arr[end]
		for (index = start; index < end; ++index) {
			if (arr[index] < arr[end]) {
				++small;
				if (small != index) swap(arr[small], arr[index]);// 这里其实可以不判断直接换
			}
		}
		// 等上面的循环结束,small指向最后一个比基准小的元素,基准在最后,中间的都是比基准大的元素
		// 现在需要把基准放到它应该在的位置,最后做一次上面的交换动作,把基准插到small的最后去,更新small后,small指向的位置就是基准
		++small;
		swap(arr[small], arr[end]);
		return small;
	}

C++ 中有没有将一个数组的一部分,比如前 4 个数组提取或者转移到另一个数组中的函数呢?可以使用copy函数

class Solution {
public:
	vector<int> getLeastNumbers(vector<int>& arr, int k) {
		QuickSort(arr, 0, arr.size() - 1, k);
		return vector<int>(arr.begin(), arr.begin() + k);
	}

	void QuickSort(vector<int>& arr, int start, int end, int k) {
		int index = Paritition(arr, start, end);
		if (start < index) QuickSort(arr, start, index - 1, k);
		if (index < (k - 1) && index < end)QuickSort(arr, index + 1, end, k);
	}

	int RandomInRange(int start, int end) {
		srand(time(nullptr));
		return rand() % (end - start + 1) + start;
	}

	int Paritition(vector<int>& arr, int start, int end) {
		int index = RandomInRange(start, end);
		swap(arr[index], arr[end]);
		int small = start - 1;
		for (index = start; index < end; ++index) {
			if (arr[index] < arr[end]) {
				++small;
				if (small != index) swap(arr[small], arr[index]);
			}
		}
		++small;
		swap(arr[small], arr[end]);
		return small;
	}
};

感觉时间复杂度并没有好到哪儿去,这个剪枝意义不大,还不如直接 sort

	vector<int> getLeastNumbers(vector<int>& arr, int k) {
		sort(arr.begin(), arr.end());
		return vector<int>(arr.begin(), arr.begin() + k);
	}

另外我注意到的为什么每次选择随机数然后与末尾交换,直接选择末尾元素作为基准不是更省事的问题,选择随机数可以在某种程度上避免性能下降的情况,例如输入数组已经基本有序的情况下,快速排序的分割不均匀,导致递归深度增加

标签:index,arr,end,Offer,int,个数,40,start,small
From: https://www.cnblogs.com/yaocy/p/17637912.html

相关文章

  • 《408操作系统 》复习笔记 ② 第二章 进程与线程
    进程的概念、组成、特征程序是静态的,存放在磁盘里的可执行文件,就是一系列的指令集合进程(Process)是动态的,是程序的一次执行过程。同一个程序多次执行会对应多个进程操作系统如何区分各个进程当进程被创建时,操作系统为该进程分配一个唯一的、不重复的PIDPCB操作系统要记......
  • 根据键名多少来生成配对,超过键名个数的键值被忽略 默认遍历keys()
    foriin{k:vfork,vinzip(range(10,40,10),range(3))}:#默认遍历keys()print(i)foriin{k:vfork,vinzip(range(10,40,10),range(3))}.items():#遍历元组print(i){k:vfork,vinzip(range(10,30,10),range(30))}#根据键名多少来生成配对......
  • Python练习:输入一个整数,输出该数二进制表示中1的个数。
      Python3整数对象存储为无符号数加上符号位标志,所以不存在“负数”补码形式,因此,计算“1”的数量需要按去符号后的无符号数:cnt=bin(n).count('1')另外,Python3无长整,整数长度原则上不限,所以不能以假定的32位处理。    补码+原码=2**321#-*-coding:ut......
  • 判断一个数是否为素数的自制函数“determine"
    intdetermine(intx){ inti=1; for(i=2;i<x;i++) { if(x%i==0) {  printf("非素数\n");  break;     } } if(i==x) printf("素数\n"); return0; }intmain(){ inta=0; scanf("%d",&a......
  • 剑指 Offer 55 - I. 二叉树的深度(简单)
    题目:classSolution{public:voidtraversal(TreeNode*cur,int&max,intdepth){//max用来记录最长路径长度,depth记录当前路径长度if(!cur)return;depth++;if(depth>max)max=depth;traversal(cur->left,max,depth);......
  • 剑指 Offer 54. 二叉搜索树的第k大节点
    方法一:由于是有序的平衡二叉树,因此是中序。根据dfs中序迭代求得递增排序后,再反转就可求得结果。classSolution{public:vector<int>tmp;intkthLargest(TreeNode*root,intk){//if(root!=NULL)returndfs(root);reverse(tmp.be......
  • arc139,arc140,arc141题解
    ARC139A-DATrailingZeros憨的。BMakeN感觉没有那么naive。首先用\(1\)去更新一下后面两个决策的价值。然后有一个较为显然的东西是说\(\text{lcm}\)为周期,周期内应该贪心取最大的。周期外由于范围很小,可以直接枚举一种决策的次数,取最小值即可。复杂度是正确的。CO......
  • 剑指 Offer 36. 二叉搜索树与双向链表
    本题比较重要的有两点:1.一般认为有序的二叉搜索树,都是中序遍历。2.中序遍历的递归顺序,得到的就是排好序的,就是链表的顺序,因此只需管遍历的过程中的链表指向即可。classSolution{public://pre将来指向尾节点,head指向头节点Node*pre=nullptr,*head=nullptr;......
  • 洛谷_[P4084]Barn Painting G题解
    题目链接这题我们可以定义一个二维的dp数组,在dp[i][j]中:i表示对于节点i,j有1,2,3三种状态,表示当点i选择被染成颜色j时,以i为根的这颗子树有多少种染色方法。那么根据乘法原理,节点i的方案数肯定等于i的每个儿子的方案数量之积。这道题整个挺简单的,剩下细节......
  • 代码随想录算法训练营第六天|242.有效的字母异位词 349. 两个数组的交集 202. 快乐数
     哈希表部分:哈希表,简单来说就是k-v形式查询的结构,用来快速判断一个元素是否出现集合里,如hashmap核心是哈希函数,k存哈希函数的值,找的时候找查询项的哈希函数值就行,返回v 出现哈希碰撞的时候,查找的流程怎么走呢?(*存疑,之后查一下) 类型:数组+集合set(set、multiset、unordered......