首页 > 编程语言 >常用查找算法

常用查找算法

时间：2022-11-12 12:14:29浏览次数：41  
标签：常用 end 迭代 back Person 算法 查找 push

5.2 常用查找算法

学习目标：

  • 掌握常用的查找算法

算法简介：

  • find //查找元素
  • find_if //按条件查找元素
  • adjacent_find //查找相邻重复元素
  • binary_search //二分查找法
  • count //统计元素个数
  • count_if //按条件统计元素个数

5.2.1 find

功能描述：

  • 查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()

函数原型：

  • find(iterator beg, iterator end, value);

    // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

    // beg 开始迭代器

    // end 结束迭代器

    // value 查找的元素

示例：

#include <algorithm>
#include <vector>
#include <string>
void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i + 1);
	}

	//内置数据类型查找
	//查找容器中是否有 5 这个元素
	vector<int>::iterator it = find(v.begin(), v.end(), 5);

	//可以发现find()返回的迭代器，如果没有找到则返回v.end()
	if (it == v.end()) 
	{
		cout << "没有找到!" << endl;
	}
	else 
	{
		cout << "找到:" << *it << endl;
	}
}

class Person {
public:
	Person(string name, int age) 
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	//重载==
	bool operator==(const Person& p) 
	{
		if (this->m_Name == p.m_Name && this->m_Age == p.m_Age) 
		{
			return true;
		}
		return false;
	}

public:
	string m_Name;
	int m_Age;
};

void test02() {

	vector<Person> v;

	//创建数据
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	//自定义数据类型查找
	//自定义数据类型查找中，判断两个自定义数据是否相等时需要考虑重载==
	vector<Person>::iterator it = find(v.begin(), v.end(), p2);
	if (it == v.end()) 
	{
		cout << "没有找到!" << endl;
	}
	else 
	{
		cout << "找到姓名:" << it->m_Name << " 年龄: " << it->m_Age << endl;
	}
}

总结： 利用find可以在容器中找指定的元素，返回值是迭代器

5.2.2 find_if

功能描述：

  • 按条件查找元素

函数原型：

  • find_if(iterator beg, iterator end, _Pred);

    // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

    // beg 开始迭代器

    // end 结束迭代器

    // _Pred 函数或者谓词（返回bool类型的仿函数）

示例：

#include <algorithm>
#include <vector>
#include <string>

//内置数据类型
class GreaterFive
{
public:
	bool operator()(int val)
	{
		return val > 5;
	}
};

void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i + 1);
	}

	//find_if：最后一个参数是谓词或者函数。遍历取出的每个数据都要当作实参传入函数中
	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
	if (it == v.end()) {
		cout << "没有找到!" << endl;
	}
	else {
		cout << "找到大于5的数字:" << *it << endl;
	}
}

//自定义数据类型
class Person {
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
public:
	string m_Name;
	int m_Age;
};

class Greater20
{
public:
	bool operator()(Person &p)
	{
		return p.m_Age > 20;
	}

};

void test02() {

	vector<Person> v;

	//创建数据
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	//自定义数据类型按条件查找-遍历后的每个结果当作实参传入到写的谓词或者函数中
	vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20());
	if (it == v.end())
	{
		cout << "没有找到!" << endl;
	}
	else
	{
		cout << "找到姓名:" << it->m_Name << " 年龄: " << it->m_Age << endl;
	}
}

int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

总结：find_if按条件查找使查找更加灵活，提供的仿函数可以改变不同的策略

5.2.3 adjacent_find

功能描述：

  • 查找相邻重复元素

函数原型：

  • adjacent_find(iterator beg, iterator end);

    // 查找相邻重复元素,返回相邻元素的第一个位置的迭代器

    // beg 开始迭代器

    // end 结束迭代器

    ​

示例：

#include <algorithm>
#include <vector>

void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(5);
	v.push_back(2);
	v.push_back(4);
	v.push_back(4);
	v.push_back(3);

	//查找相邻重复元素
	vector<int>::iterator it = adjacent_find(v.begin(), v.end());
	if (it == v.end()) {
		cout << "找不到!" << endl;
	}
	else {
		cout << "找到相邻重复元素为:" << *it << endl;
	}
}

总结：面试题中如果出现查找相邻重复元素，记得用STL中的adjacent_find算法

功能描述：

  • 查找指定元素是否存在

函数原型：

  • bool binary_search(iterator beg, iterator end, value);

    // 查找指定的元素，查到（可以发现返回的是bool类型） 返回true 否则false

    // 注意: 在无序序列中不可用，而且必须是升序

    // beg 开始迭代器

    // end 结束迭代器

    // value 查找的元素

示例：

#include <algorithm>
#include <vector>

void test01()
{
	vector<int>v;

	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	//二分查找
	bool ret = binary_search(v.begin(), v.end(),2);
	if (ret)
	{
		cout << "找到了" << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
}

int main() {

	test01();

	system("pause");

	return 0;
}

总结：二分查找法查找效率很高，值得注意的是查找的容器中元素必须的有序序列

5.2.5 count

功能描述：

  • 统计元素个数

函数原型：

  • count(iterator beg, iterator end, value);

    // 统计元素出现次数

    // beg 开始迭代器

    // end 结束迭代器

    // value 统计的元素

示例：

#include <algorithm>
#include <vector>

//内置数据类型
void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(5);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);

	int num = count(v.begin(), v.end(), 4);

	cout << "4的个数为： " << num << endl;
}

//自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	//在比较两个自定义数据类型是否相等时需要重写 ==
	bool operator==(const Person & p)
	{
		if (this->m_Age == p.m_Age)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	string m_Name;
	int m_Age;
};

void test02()
{
	vector<Person> v;

	Person p1("刘备", 35);
	Person p2("关羽", 35);
	Person p3("张飞", 35);
	Person p4("赵云", 30);
	Person p5("曹操", 25);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);
    
    Person p("诸葛亮",35);

	int num = count(v.begin(), v.end(), p);
	cout << "num = " << num << endl;
}
int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

总结： 统计自定义数据类型时候，需要配合重载 operator==

5.2.6 count_if

功能描述：

  • 按条件统计元素个数

函数原型：

  • count_if(iterator beg, iterator end, _Pred);

    // 按条件统计元素出现次数

    // beg 开始迭代器

    // end 结束迭代器

    // _Pred 谓词或者函数

    ​

示例：

#include <algorithm>
#include <vector>

class Greater4
{
public:
	bool operator()(int val)
	{
		return val >= 4;
	}
};

//内置数据类型
void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(5);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);

	//谓词都是将遍历得到的数据作为函数实参
	int num = count_if(v.begin(), v.end(), Greater4());

	cout << "大于4的个数为： " << num << endl;
}

//自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;
};

class AgeLess35
{
public:
	bool operator()(const Person &p)
	{
		return p.m_Age < 35;
	}
};
void test02()
{
	vector<Person> v;

	Person p1("刘备", 35);
	Person p2("关羽", 35);
	Person p3("张飞", 35);
	Person p4("赵云", 30);
	Person p5("曹操", 25);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	int num = count_if(v.begin(), v.end(), AgeLess35());
	cout << "小于35岁的个数：" << num << endl;
}


int main() {

	//test01();

	test02();

	system("pause");

	return 0;
}

总结：按值统计用count，按条件统计用count_if

标签：常用,end,迭代,back,Person,算法,查找,push
From： https://www.cnblogs.com/xiaoqing-ing/p/16883417.html

相关文章

  • 常用排序算法
    5.3常用排序算法学习目标：掌握常用的排序算法算法简介：sort//对容器内元素进行排序random_shuffle//洗牌指定范围内的元素随机调整次序merge......
  • 常用遍历算法
    5.1常用遍历算法学习目标：掌握常用的遍历算法算法简介：for_each//遍历容器transform//搬运容器到另一个容器中5.1.1for_each功能描述：实现遍历容器......
  • 【雷达通信】基于均匀圆阵下CA-MUSIC的二维DOA估计算法附matlab代码
    ✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进。......
  • 【雷达通信】基于均匀圆阵下CA-MUSIC的二维DOA估计算法附matlab代码
    ✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进。......
  • SpringBoot 03: 常用web组件 - - - 拦截器 + Servlet + 过滤器
    常用web组件拦截器Servlet过滤器使用思想创建自定义类实现或者继承框架里的接口或类将自定义类注册到框架中使用自定义类拦截器说明拦截器是SpringMVC中的......
  • 查找
        数组和索引 ......
  • MFC-QT校园导航系统（旅行商TSP算法）
    MFC-QT校园导航系统（旅行商TSP算法）[问题描述]旅行商问题，给定若干城市和城市间距离，求解访问每一座城市一次并回到起始城市的最短回路。想象一个校园场景:某同学从宿舍出发......
  • 实验三：朴素贝叶斯算法实验
    【实验目的】理解朴素贝叶斯算法原理，掌握朴素贝叶斯算法框架。【实验内容】针对下表中的数据，编写python程序实现朴素贝叶斯算法（不使用sklearn包），对输入数据进行预测；熟悉s......
  • [回溯算法]leetcode216. 组合总和 III(c实现)
    题目找出所有相加之和为 n的 k 个数的组合，且满足下列条件：只使用数字1到9每个数字 最多使用一次 返回所有可能的有效组合的列表。该列表不能包含相同的组合两次......
  • KMP算法
    KMP算法是一个字符串匹配算法，或者说是一个子字符串匹配算法算法在字符串str中搜索子串pattern，如果存在，返回这个子串的起始索引，如果不存在，返回-1暴力枚举匹配暴力的字符......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99