当前位置：首页 > news >正文

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

news 来源：原创 2024/5/7 12:29:59

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

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

6d4ffada7fe0312172f742dc9409ec40

文章目录

- - 33.最大公约数
  - - 输入格式
    - 输出格式
    - 数据范围
    - 输入样例：
    - 输出样例：
    - 思路
  - 34.数组去重
  - - 输入格式
    - 输出格式
    - 数据范围
    - 输入样例：
    - 输出样例：
    - 思路
    - sort自定义排序函数
    - - 1.sort简介
      - 2.使用方法

33.最大公约数

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

输入格式

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

输出格式

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

数据范围

1≤a,b≤1000

输入样例：

12 16

输出样例：

思路

常见思路：利用循环求解

#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 辗转相除法（欧几里得算法）
前置定理： $g c d (a, b) = g c d (b, am o d b)$

可以一直将 $g c d (a, b)$ 转化为 $g c d (x, 0)$ ，此时 x 为 $g c d (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

输出样例：

思路

第一种思路：

采取分别对每个数字出现的次数计数，最后再统计出现次数不为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;
}