每日算法刷题Day11-最大公约数、数组去重

⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。

🔥本文已收录于算法刷题系列专栏： 每日算法题解 欢迎订阅，持续更新。

33.最大公约数

输入两个整数 a 和 b，请你编写一个函数，int gcd(int a, int b), 计算并输出 a 和 b 的最大公约数。

输入格式

共一行，包含两个整数 a 和 b。

输出格式

共一行，包含一个整数，表示 a 和 b 的最大公约数。

数据范围

1≤a,b≤1000

输入样例：

12 16

输出样例：

4

思路

常见思路：利用循环求解

#include
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。

输入样例：

5
1 1 2 4 5

输出样例：

4

思路

第一种思路：

采取分别对每个数字出现的次数计数，最后再统计出现次数不为0的个数。

#include
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
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
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的方式进行排序。也可以不写第三个参数，此时按默认排序，从小到大进行排序。