欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构算法--查找算法实例解析

程序员文章站 2022-12-04 20:57:48
@(Aaron) [LeetCode, C++]主要内容包括:查找算法实例讲解文章目录1、查找算法简介1.1 顺序查找1.2 二分查找2、实例讲解2.1 搜索插入位置2.2 快乐数2.3 同构字符串1、查找算法简介1.1 顺序查找核心: 从数据的第一个元素开始,依次比较,直到找到目标数据或查找失败。从表中的第一个元素开始,依次与关键字比较。若某个元素匹配关键字,则 查找成功。若查找到最后一个元素还未匹配关键字,则 查找失败。时间复杂度: 顺序查找平均关键字匹配次数为...

@(Aaron) [LeetCode, C++]

主要内容包括:

  • 查找算法

  • 实例讲解




1、查找算法简介

数据结构算法--查找算法实例解析

1.1 顺序查找

核心: 从数据的第一个元素开始,依次比较,直到找到目标数据或查找失败。

  1. 从表中的第一个元素开始,依次与关键字比较。
  2. 若某个元素匹配关键字,则 查找成功。
  3. 若查找到最后一个元素还未匹配关键字,则 查找失败。

时间复杂度: 顺序查找平均关键字匹配次数为表长的一半,其时间复杂度为O(n)。

顺序查找的评估: 顺序查找的优点是对表无要求,插入数据可在O(1)内完成。缺点是时间复杂度较大,数据规模较大时,效率较低。

1.2 二分查找

也称折半查找,查找性能优异,但查找数据必须是有序序列。

核心: 先确定待查目标所在的范围,然后逐步缩小范围直到查找成功或查找失败。

关键字key与表中某一元素Array[i]比较,有3中结果:

  1. key==Array[i],查找成功。
  2. key > Array[i],待查元素可能的范围是Array[i]之前。
  3. 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
解释:
12+92=821^{2} + 9^{2} = 82
82+22=688^2 + 2^2 = 68
62+82=1006^2 + 8^2 = 100
12+02+02=11^2 + 0^2 + 0^2 = 1

经过观察我们发现总共有三种情况:

  1. 最终会得到 1。
  2. 最终会进入循环。
  3. 值会越来越大,最后接近无穷大。

对于第三种情况:当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

相关标签: 算法 数据结构