每日算法刷题Day11-最大公约数、数组去重
每日算法刷题Day11-最大公约数、数组去重
⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。 🔥本文已收录于算法刷题系列专栏： 每日算法题解 欢迎订阅，持续更新。
文章目录
33.最大公约数
输入两个整数 a 和 b，请你编写一个函数，int gcd(int a, int b), 计算并输出 a 和 b 的最大公约数。
输入格式
共一行，包含两个整数 a 和 b。
输出格式
共一行，包含一个整数，表示 a 和 b 的最大公约数。
数据范围
1≤a,b≤1000
输入样例：
12 16输出样例：
4思路
常见思路：利用循环求解
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
for(int i = min(a,b);i >=1;i--)
{
if(b%i==0 && a%i == 0)return i;
}
}
int main()
{
int a,b;
cin>>a>>b;
cout<< gcd(a,b)<<endl;
return 0;
}此外可以采用欧几里得算法解决（辗转相除法）
part2 辗转相除法（欧几里得算法） 前置定理：gcd(a,b) = gcd(b,a mod b) 可以一直将 gcd(a,b) 转化为 gcd(x,0) ，此时 x 为 gcd(a,b) 。
代码：
while (b) {
int tmp = a % b;
a = b;
b = tmp;
}时间复杂度 O(log2(a+b))。
34.数组去重
给定一个长度为 n 的数组 a，请你编写一个函数：
int get_unique_count(int a[], int n); // 返回数组前n个数中的不同数的个数输入格式
第一行包含一个整数 n。
第二行包含 n 个整数，表示数组a。
输出格式
共一行，包含一个整数表示数组中不同数的个数。
数据范围
1≤n≤1000, 1≤ai≤1000。
输入样例：
5
1 1 2 4 5输出样例：
4思路
第一种思路：
采取分别对每个数字出现的次数计数，最后再统计出现次数不为0的个数。
#include<bits/stdc++.h>
using namespace std;
int get_unique_count(int a[],int n)
{
int cnt[1001] = {0},tot = 0;
for(int i = 0 ; i < n; i++)
{
for(int j = 0; j <= 1000; j++){
if(a[i] == j )cnt[a[i]]++;}
}
for(int i = 0; i <= 1000; i++)
if(cnt[i] != 0)tot++;
cout<< tot<<endl;
}
int main()
{
int n,a[1001];
cin >> n;
for(int i = 0; i < n; i++)cin >> a[i];
get_unique_count(a , n);
return 0;
}第二种思路：
采取判断该数之前是否出现过。用bool做标记。
#include<bits/stdc++.h>
using namespace std;
int get_unique_count(int a[],int n)
{
int cnt = 0;
for(int i = 0; i < n; i++)
{//本次要比较的数
bool occurred = false;
for(int j = 0; j < i; j++)
{//前面所有的数
if(a[i] == a[j])
{
occurred = true;
break;
}
}
if(occurred == false)cnt ++;
}
return cnt;
}
int main()
{
int n,a[1001];
cin >> n;
for(int i = 0; i < n; i++)cin >> a[i];
cout << get_unique_count(a , n);
return 0;
}第三种思路：
先对数组进行排序，这时会把数字相同的排序在一起，再使用双指针方法去重，最后统计前一个指针的数目即可。
#include<bits/stdc++.h>
using namespace std;
int get_unique_count(int a[],int n)
{
int k = 1;//第一个指针
for(int j = 1; j < n ; j++)
{//第二个指针
if(a[j] != a[k-1])
a[k++] = a[j];//如果不相等，标记一下
}
return k;
}
int main()
{
int n,a[1001];
cin >> n;
for(int i = 0; i < n; i++)cin >> a[i];
sort(a, a+n);//注意需要提前由小到大排序好
cout << get_unique_count(a , n);
return 0;
}sort自定义排序函数
1.sort简介
（1）用于C++中，对给定区间所有元素进行排序；
（2）使用的排序方法是类似于快排的方法，时间复杂度为n*log2(n)，执行效率较高；
（3）头文件 #include 。
2.使用方法
sort函数有三个参数
sort(first,last,cmp);
其中，first是元素的起始地址，last是结束地址，cmp是排序的方式。对**[first，last)（一定要注意这里的区间是左闭又开）**区间内数据根据cmp的方式进行排序。也可以不写第三个参数，此时按默认排序，从小到大进行排序。
腾讯云开发者
