删除重复数字的三种方法(详解)
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
前言本期是关于去重数字的三种方法详解今天你c了吗
输入描述
第一行输入一个整数n表示序列有n个整数。
第二行输入n个整数每个整数大于等于1小于等于1000整数之间用空格分隔。
输出描述
去重并且从小到大排列的整数序列整数之间用空格分隔。
示例1
输入
6 5 3 3 4 2 2
输出
2 3 4 5
方法一覆盖法暴力求解
代码实现
int main()
{
int n = 0;
scanf("%d", &n);
int i = 0;
int arr[1000] = { 0 };
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
//冒泡排序
for (i = 0; i < n - 1; i++)
{
int j = 0;
for (j = 0; j < n - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
//去重
for (i = 0; i < n - 1; i++)
{
if (arr[i] == arr[i + 1])
{
int k = 0;
for (k = i; k < n - 1; k++)
{
arr[k] = arr[k + 1];
}
n--;
i--;
}
}
//打印
for (i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
思路
1. 将无序数组变成有序数组这里使用冒泡排序点击即跳转我另一篇博客的详解
2. 两两进行比较若是二者值相同则出现了重复数字用后者覆盖前者覆盖后相当于删除了一个重复数字数字个数-1
3. 需要对新覆盖上来的数字再和它后一位数字进行比较比如出现连续3个及以上的重复数字
代码解读详解去重部分
已经实现过数组排序
for (i = 0; i < n - 1; i++)
{
if (arr[i] == arr[i + 1])
{
int k = 0;
for (k = i; k < n - 1; k++)
{
arr[k] = arr[k + 1];
}
n--;
i--;
}
}
以如下为例
示例1
输入
6 5 3 3 4 2 2
输出
2 3 4 5
1.数字之间两两比较6个数字共需比较5次故而n个数字需比较n-1次
这里的for循环用于实现比较的次数
for (i = 0; i < n - 1; i++)
2.for循环内部两个数字之间的一次比较
if (arr[i] == arr[i + 1])
{
int k = 0;
for (k = i; k < n - 1; k++)
{
arr[k] = arr[k + 1];
}
n--;
i--;
}
若是两个数字相同则出现重复数字需要去重用后者覆盖前者
如 5 3 3 4 2 2经过前面的冒泡排序后变成2 2 3 3 4 5
假设现在比较的是2 2 两个数字需要进行去重操作如下
从第二个2开始的全部数字往前移动一位
移动完成后删重成功数字个数-1
注意特殊情况出现连续的3个及以上的重复数字如 2 2 2 3 3 4 5
第一个2和第二个2经过去重后数组变成2 2 3 3 4 5
原本比较完第一个元素和第二个元素后下一次是比较第二个元素和第三个元素
但是第二个元素是2第三个元素是3我们漏掉了新的第一个元素2和第二个元素2的比较
2和3不同不去重下一次再比较3和3进行去重后数组变成2 2 3 4 5
故而我们在每一次去重后都需要对新覆盖上来的数字原本是两两比较的重复数字中的第二个数和它后面的一个数进行再次比较
操作是i--
形象一点假设一个数字的下标为2一个数字的下标为3此时的i=2i+1=3
本来这轮的两个数字去重后马上要进行的是下一对的比较
在进入下一对的比较之前i--相当于退后一步然后i++进入下一对比较
效果是先退一步再前进一步=原地不动
原本 下一轮要比较的两个数字的下标为3和下标为4但是在这之前i--退后一步
i2-1=1i变成了下标1i++i1+1=2此时i还是下标2又可以对下标为2的数字
和下标为3的数字进行再次比较
方法二简单
代码实现
int main()
{
int n = 0;
scanf("%d", &n);
int i = 0;
int arr[1001] = { 0 };
int input = 0;
for (i = 0; i < n; i++)
{
scanf("%d", &input);
arr[input] = input;
}
for (i = 0; i < 1001; i++)
{
if (arr[i] != 0)
{
printf("%d ", arr[i]);
}
}
return 0;
}
思路
1.将每一个数字作为下标将其对应的数组空间内置成数字的值
2. 打印数组中不为0的值
如5 3 3 4 2 2
值 | 0 | 0 | 2 | 3 | 4 | 5 |
下标 | 0 | 1 | 2 | 3 | 4 | 5 |
两个重复的数字3和2存入数组中在下标为3和下标为2的空间中存了一个3和一个2的值
初始化数组的内容全部为0最后打印不为0的值
方法三双指针
双指针详解我的另一篇博客已有详解点击即跳转