前言:本期是关于去重数字的三种方法详解,今天你c了吗?

输入描述:

第一行,输入一个整数n,表示序列有n个整数。

第二行输入n个整数(每个整数大于等于1,小于等于1000),整数之间用空格分隔。

输出描述:

去重并且从小到大排列的整数序列,整数之间用空格分隔。

示例1

输入:

65 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  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

输入:

65 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=2,i+1=3

本来这轮的两个数字去重后,马上要进行的是下一对的比较

在进入下一对的比较之前,i–,相当于退后一步,然后i++,进入下一对比较

效果是:先退一步再前进一步=原地不动

原本 下一轮要比较的两个数字的下标为3和下标为4,但是在这之前i–(退后一步)

i:2-1=1,i变成了下标1,i++,i:1+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

002345
下标012345

两个重复的数字3和2存入数组中,在下标为3和下标为2的空间中存了一个3和一个2的值

初始化数组的内容全部为0,最后打印不为0的值

方法三:双指针

双指针法​​​​​​​(我的另一篇博客已有详解,点击即跳转)