行百里者半九十 —— 查找算法
2021/11/18 9:09:54
本文主要是介绍行百里者半九十 —— 查找算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
------------恢复内容开始------------
剑指 Offer 03. 数组中重复的数字
剑指 Offer 53 - I. 在排序数组中查找数字 I
剑指 Offer 53 - II. 0~n-1 中缺失的数字
1、找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
该题有多种解法,要明确出题人的意图,是时间优先还是空间优先
1) 空间优先:空间O(1),时间O(nLogn)
先排序,再查看相邻元素是否相同
1 class Solution{ 2 public: 3 int findRepeatNumber(vector<int>& nums) { 4 sort(nums.begin(), nums.end()); 5 for(int i = 0; i < nums.size()-1; i++) { 6 if(nums[i] == nums[i+1]){ 7 return nums[i]; 8 } 9 } return -1; 10 } 11 };
2) 时间优先:空间O(n),时间O(n)
哈希表,每次存储时检查是否有重复的元素
1 class Solution{ 2 public: 3 int findRepeatNumber(vector<int>& nums) { 4 unordered_map<int, int> mp; 5 for(int i = 0; i < nums.size(); i++){ 6 if(mp.find(nums[i]) != mp.end()) return nums[i]; 7 else mp[nums[i]] ++; 8 } 9 return -1; 10 } 11 };
2、在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
该题一般是考察二分法 时间复杂度O(logn), 空间复杂度O(1)
1 class Solution { 2 public: 3 int search(vector<int>& nums, int target) { 4 int length = nums.size(); 5 int left = 0; 6 int right = length -1; 7 while(left < right) { //非递减数组 8 int mid = (left + right)/2; 9 if(nums[mid] >= target) right = mid; 10 if(nums[mid] < target) left = mid; 11 } 12 int count = 0; 13 while(nums[left++] == target) 14 count++; 15 return count; 16 } 17 };
3、0~n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
1 class Solution { 2 public: 3 int missingNumber(vector<int>& nums) { 4 int length = nums.size(); 5 int left = 0; 6 int right = length -1; 7 8 while(left < right) { //非递减数组 9 int mid = (left + right)/2; 10 if(nums[mid] == mid) left = mid; //注意是mid+1 11 else right = mid; 12 } 13 if(nums[left] != left ) 14 return left; 15 else 16 return left+1; //0~n-1的数组,恰好n不在其中[0,1,2,3] 17 return -1; 18 } 19 };
对于有序的数组, 都应该想到用二分法搜索
这篇关于行百里者半九十 —— 查找算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现