题解记录

两道OJ题

Question 1

这个题并不是很难，读完题脑子里的第一反应就是遍历整个数组，把满足条件的值剔除，再返回新数组的长度就行了。整个逻辑还是比较清晰的。

画个图，帮助我们更清楚的理解：

(图片)

把p假想成一个指针，现在的问题就是怎么用代码把图片表达的想法表示出来。由于使用覆盖的方法把数组中的值“剔除”，所以遇到满足条件时，“指针”p是不需要移动的，这点很重要。

第一次我使用for循环遍历数组，遇到目标值就覆盖，并记录覆盖的次数以返回新数组的长度：

int removeElement(int* nums, int numsSize, int val){
    int p = 0, count = 0;
    for(int i = 0; i < numsSize; i++)
    {
        if(nums[i-count] == val)
        {
            for(p = i - count; p < numsSize - 1; p++)
            {
                nums[p] = nums[p+1];
            }
            count++;
        }
    }
    return numsSize - count;
}

用for循环遍历数组时，如果遇到满足条件的值，覆盖以后，“指针”p是不需要向后移动的，但每循环一次，i就会做一次自增，所以需要对p做一定的修改。用count记录覆盖了几次，同时用 i - count，可以有对“指针”p的回溯效果。我在这里错了好几次才发现需要减去count 。

同时，我觉得这个题使用while循环会比for循环更方便，因为不会被 i 的值折磨 :

int removeElement(int* nums, int numsSize, int val){
    int p = 0, count = 0;
    int changetimes = 0;
    while(count < numsSize)
    {
        if(nums[p] == val)
        {
            for(int i = p; i < numsSize - 1; i++)
            {
                nums[i] = nums[i+1];
            }
            changetimes++;
        }
        else
        {
            p++;
        }
        count++;
    }
    return numsSize - changetimes;
}

分析上面算法的时间复杂度，考虑最坏的情况：数组中的每个值都是目标值。那覆盖的操作要进行：

(n-1)+(n-2)+\cdots+2+1

这么多次，上式是一个等差数列，可得它的时间复杂度是

O(n^2)

, 空间复杂度是

O(1)

。跳出题目的限制，考虑能不能优化上述算法，使其时间复杂度为

O(n)

？

尝试用空间复杂度去换时间复杂度，也就是额外开辟一块空间来辅助完成任务。和上一种方法的思路类似。可以再开辟一个和原数组大小相同的数组，然后遍历一遍题目所给的数组，将所有符合条件的值搬到新数组中，并记录次数，然后把新数组复制给原数组。具体代码如下：

int removeElement(int* nums, int numsSize, int val){
    int a[100] = { 0 };
	int count = 0;
	for (int i = 0; i < numsSize; i++)
	{
		if (nums[i] != val)
		{
			a[count] = nums[i];
            count++;
		}
	}
	for (int i = 0; i <= count; i++)
	{
		nums[i] = a[i];
	}
	return count;
}

相比于上一个解法，降低了时间复杂度，但是空间复杂度提高了。本题要求我们不使用额外的空间，所以此解法是不满足要求的，只是提供一种额外的想法。

有没有可能找到一种算法，只遍历一遍数组而不使用额外的空间，也就是时间复杂度为 $O(n)$ ,空间复杂度为 $O(1)$ 呢？答案是肯定的，只遍历一遍，在原数组的基础上修改就行。这时我们可以利用“双指针”来完成，其基本思路如下图：

（图片）

代码如下：

int removeElement(int* nums, int numsSize, int val){
    int src = 0, dst = 0;
    while(src < numsSize)
    {
        if(nums[src] != val)
        {
            nums[dst] = nums[src];
            src++;
            dst++;
        }
        else
        {
            src++;
        }
    }
    return dst;
}

本题不算难，但最优解往往是不容易想到的，这种由浅及深，一步步优化算法的思想是值得我学习的，我认为这种品质是难得的。

Question2

[删除有序数组中的重复项]

由于给定的数组是升序排列的，所以数组中出现的重复元素都是连续的（比如1 2 2 2 3）这种，重复的数字都是一段一段的，扫描整个数组如果发现前后两个数字不同，那就比较下两个。如果相同，那只用移动后面的那个“指针”，直到找到第一个不同的数字，就说明走完了这个相同数字的一段。然后将这个不同的数字覆盖到第一个相同数字的后面。文字描述比较繁琐，直接上图：

（图片）

int removeDuplicates(int* nums, int numsSize){
    int i = 0, j = 1, dst = 0;
    for(j = 1; j < numsSize; )
    {
        if(nums[i] == nums[j])
        {
            j++;
        }
        else
        {
            nums[dst] = nums[i];
            i = j;
            j++;
            dst++;
        }
    }
    nums[dst] = nums[i];
    return dst + 1;
}

这题比上题的第三种解法还多用了一个“指针”，其实也不太好想，只好积累下来罢。

最近学习效率不高，状态低迷，网课欠下了许多债，内容学起来也不轻松，简直就是折磨啊。。。。。。想了想还是赶紧补完这篇吧，不然这写了一半的东西再拖恐怕就烂尾了。（=.=

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。