C语言每日亿题(二)

一.删除有序数组的重复项

原题传送门：力扣

题目：

题目的大概意思是：给你一个数组，你把数组里的重复项的数字删掉只保留一个，然后返回删除之后数组的大小。并且不能开辟新的数组空间。

方法其实很简单，我们在这里定义两个指针：

先向后遍历指针p1,如果p1指向的元素和p2指向的元素相等，p1不管继续向后走：

此时发现p1指向的元素和p2指向的元素不相等了。我们先将p2向后挪一个位置：

然后再将p1,p2指向的元素互换，换完之后p1在向后走一步：

就这样一直循环判断，但是什么时候截止呢？

经过我们一步一步的移动，发现最后一个4在和p2指向的元素交换完之后，p1还要向后挪动一步，此时p1指向的是数组的末尾，所以说循环结束的条件是判断p1指向的位置是否是数组末尾即可：

while(p1 != nums + numsSize)
1

通过上面的步骤，循环里的内容也可以写出来了：

	int* p1 = nums;
    int* p2 = nums;
    while(p1 != nums + numsSize)
    {
        if(*p1 == *p2)
        {
            p1++;
        }
        else
        {
            p2++;
            //交换
            int tmp = *p1;
            *p1 = *p2;
            *p2 = tmp;
            p1++;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

但是我们最后还有一个问题，返回什么值？题目要求的是返回删除完之后的个数，也就是我们要计算下面画方框的这些元素的个数：

我们看在移动之前时p2指向的位置：

在刚开始时p2指向的是第一个元素，每替换一次p2向后移动一步，是不是可以认为刚开始元素的个数为1，每替换一次，p2++,元素的个数+1.在这里我们总共替换了4次，所以数组总大小应该是5是不是合情合理。

int removeDuplicates(int* nums, int numsSize){
    int* p1 = nums;
    int* p2 = nums;
    int flag = 1;

    while(p1 != nums + numsSize)
    {
        if(*p1 == *p2)
        {
            p1++;
        }
        else
        {
            p2++;
            //交换
            int tmp = *p1;
            *p1 = *p2;
            *p2 = tmp;
            p1++;
            flag++;
        }
    }
    return flag;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

所以我们定义一个变量flag,每替换一次flag++.最后返回flag就行。

但是有人可能回想，你数组后面那一坨也没去掉啊，做题目时检查不出来吗？我们看题目的评判标准：

可以发现在看你写的数组对不对的时候，只关心你数组前k个元素是否正确，这个k就是我们返回的flag的值。也就是它根本不会担心你数组后面的内容是什么。

二.移除元素

原题传送门：力扣
题目：


和第一题类似，都是返回删除后数组里元素的个数，但是这一题删除的是固定的值。方法我们应该也可以用一样的。

现在我们需要删除掉这个数组里的2，同样可以定义两个指针：

首先我们还是老办法，遍历指针p1.
但是看好我接下来的操作，如果p1指向的元素不等于val，就把此时p1,p2指向的内容互换，然后两个指针分别向后走一步：

如果p1指向的内容相等呢？我们不管p1向后走：

可能刚才有人不理解p1,p2为什么要交换，但是我们看现在这一步发现p1指向的内容又不一样了，这样我们交换是不是就可以把val相对应的值移到后面去了？

然后我们继续走，只要p1指向的元素不相等就交换：

其实到这里已经换好了，最后p1++指向了数组的末尾然后结束。

    while (p1 != nums + numsSize)
    {
        if (*p1 != val)
        {
            int tmp = *p1;
            *p1 = *p2;
            *p2 = tmp;
            p1++;
            p2++;
        }
        else
        {
            p1++;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

但是这一题同样要返回交换后数组的个数，我们主要观察指针p2在结束时的位置：

可以看到p2指向的位置恰好是我们新数组的末尾，是不是可以认为p2每往后走一步，新数组个数+1.然后只有在交换的时候p2才会向后走，所以我们就可以这样写：

int removeElement(int* nums, int numsSize, int val) {
    int* p1 = nums;
    int* p2 = nums;
    int flag = 0;

    while (p1 != nums + numsSize)
    {
        if (*p1 != val)
        {
            int tmp = *p1;
            *p1 = *p2;
            *p2 = tmp;
            p1++;
            p2++;
            flag++;
        }
        else
        {
            p1++;
        }
    }
    return flag;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三.移动零

我们最后再看一道超简单的题目：
原题传送门：添加链接描述

题目：

仔细看是不是和第二题基本一模一样，第二题我们可以理解为把val移动到数组末尾，现在我们稍微改进一下刚才的代码：

void moveZeroes(int* nums, int numsSize){
    int* p1 = nums;
    int* p2 = nums;

    while (p1 != nums + numsSize)
    {
        if (*p1 != 0)
        {
            int tmp = *p1;
            *p1 = *p2;
            *p2 = tmp;
            p1++;
            p2++;
        }
        else
        {
            p1++;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

把val改成0就行，而且它不需要你反悔任何东西，数组大小的判断也就不需要了。