数据结构算法--查找算法实例解析
@(Aaron) [LeetCode, C++]
主要内容包括:
-
查找算法
-
实例讲解
1、查找算法简介
1.1 顺序查找
核心: 从数据的第一个元素开始,依次比较,直到找到目标数据或查找失败。
- 从表中的第一个元素开始,依次与关键字比较。
- 若某个元素匹配关键字,则 查找成功。
- 若查找到最后一个元素还未匹配关键字,则 查找失败。
时间复杂度: 顺序查找平均关键字匹配次数为表长的一半,其时间复杂度为O(n)。
顺序查找的评估: 顺序查找的优点是对表无要求,插入数据可在O(1)内完成。缺点是时间复杂度较大,数据规模较大时,效率较低。
1.2 二分查找
也称折半查找,查找性能优异,但查找数据必须是有序序列。
核心: 先确定待查目标所在的范围,然后逐步缩小范围直到查找成功或查找失败。
关键字key与表中某一元素Array[i]比较,有3中结果:
- key==Array[i],查找成功。
- key > Array[i],待查元素可能的范围是Array[i]之前。
- key < Array[i],待查元素可能的范围是Array[i]之后。
二分查找基于上述的原理:每次将可能范围中间位置的数与key比较,相等则放回查找成功,不等则缩小范围。
时间复杂度: 二分查找的时间复杂度为 log2(N)。
二分查找的评估: 二分查找的效率较高,但要求序列有序。序列排序本身就是一种高代价操作,往有序序列内插入和删除数据都比较困难。因此,二分查找特别适合于很少改动,但需要经常查找的表。
此外还有插值查找、斐波那契查找、二叉查找树等。
2、实例讲解
2.1 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
此题明显适用二分查找:
class Solution { public: int searchInsert(vector<int>& nums, int target) { int n = nums.size(); int left = 0, right = n-1, ans = n; while(left<=right) { int mid = ((right - left) >> 1) + left; if(target <= nums[mid]) { ans = mid; right = mid - 1; } else { left = mid + 1; } } return ans; } };
2.2 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。
如果 n 是快乐数就返回 True ;不是,则返回 False 。
示例:
输入:19
输出:true
解释:
经过观察我们发现总共有三种情况:
- 最终会得到 1。
- 最终会进入循环。
- 值会越来越大,最后接近无穷大。
对于第三种情况:当n取最大的三位数999时,其下一个数为243,所以可以断定,越来越大的情况并不会出现。
对于第二种情况,需要建立一个hashmap用以查找之前出现过的数字。
class Solution { public: int getnext(int n) { int new_one = 0; while(n>0) { int temp = n%10; new_one += pow(temp, 2); n = n/10; } return new_one; } bool isHappy(int n) { unordered_map<int, int> map_set; while(n != 1 && map_set.count(n) == 0) { map_set.insert({n, 1}); n = getnext(n); } return n == 1; } };
2.3 同构字符串
给定两个字符串 s 和 t,判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。
示例 1:
输入: s = “egg”, t = “add”
输出: true
示例 2:
输入: s = “foo”, t = “bar”
输出: false
示例 3:
输入: s = “paper”, t = “title”
输出: true
说明:
你可以假设 s 和 t 具有相同的长度。
思路:对于第一个出现的字符,判断其后出现的位置是否相同。
class Solution { public: bool isIsomorphic(string s, string t) { if (0 == s.size() && 0 == t.size()) { return true; } for (int index = 0; index <= s.size() - 1; index++) { if (s.find(s[index]) != t.find(t[index])) { return false; } } return true; } };
本文地址:https://blog.csdn.net/weixin_39940512/article/details/108239176
上一篇: [LeetCode] 四数和值问题类型总结(哈希、双指针)
下一篇: 个推教程--第一课--综述