⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。
🔥本文已收录于算法刷题系列专栏： 每日算法题解 欢迎订阅，持续更新。
33.最大公约数
输入两个整数 a 和 b，请你编写一个函数，int gcd(int a, int b), 计算并输出 a 和 b 的最大公约数。
输入格式
共一行，包含两个整数 a 和 b。
输出格式
共一行，包含一个整数，表示 a 和 b 的最大公约数。
数据范围
1≤a,b≤1000
输入样例：
输出样例：
思路
常见思路：利用循环求解
#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,amodb)![]()
可以一直将 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。
输入样例：
输出样例：
思路
第一种思路：
采取分别对每个数字出现的次数计数，最后再统计出现次数不为 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 <algorithm>。
2.使用方法
sort 函数有三个参数
sort(first,last,cmp);
其中，first 是元素的起始地址，last 是结束地址，cmp 是排序的方式。对**[first，last)（一定要注意这里的区间是左闭又开）**区间内数据根据 cmp 的方式进行排序。也可以不写第三个参数，此时按默认排序，从小到大进行排序。
评论