数组去重
题目
给定一个长度为n的数组a,请你编写一个函数:
int get_unique_count(int a[], int n); // 返回数组前n个数中的不同数的个数
输入格式
第一行包含一个整数n。
第二行包含n个整数,表示数组a。
输出格式
共一行,包含一个整数表示数组中不同数的个数。
数据范围
1≤n≤1000
输入样例:
5
1 1 2 4 5
输出样例:
4
题解
题目解析
这里只需要标记每个数字是否出现即可
思路
1、循环遍历数组前size个数字
2、判断数字是否被标记
- 是:那么不再进行标记,不重复数字不增加
- 否:进行标记数字,不重复数字增加1
3、返回不重复数字
#include<iostream>
using namespace std;
const int N = 1010;
int a[N];//原数组
bool st[N];//判重数组,没赋值的数组全部存为false
int n;
//返回数组前size个数中的不同数的个数
int unique(int a[], int size)
{
int cnt = 0;//不重复数字数量
for(int i = 0;i<size;i++)
{
if(!st[a[i]]) //当st[a[i]]为false的时候,说明数字不重复
{
st[a[i]] = true;//标记数字st[a[i]]为true,当下次遍历到这个数字时,便不会进入if语句里面
cnt++;//不重复数字数量++
}
}
return cnt;//返回不重复数字数量
}
int main()
{
scanf("%d",&n);
for(int i = 0;i<n;i++) scanf("%d",&a[i]);//输入数组
printf("%d", unique(a,n));//输出
return 0;
}
太强了
厉害厉害,膜拜膜拜Orz
如果a[i] >= 1010怎么办?
题目中确实没给出输入整数的范围,但是按照题目意思,输入的整数应该都是小于等于1000的。如果
a[i]>=1010
只需要将 N 扩大为想要的范围即可。
调stl或者手写hash也行