数组相关的面试OJ题

目录

1.移除元素

方法1【暴力求解】

方法2【双指针】

2.删除两个有序数组中的重复项

方法1【双指针】

3.合并两个有序数组

方法1【暴力求解】

方法2【开辟新数组】---选择较小的尾插 

方法3【三指针】---选择较大的头插

4.有序数组的合并

方法1【三指针】 

---

写一个算法代码需要考虑：起始条件，中间过程，结束条件。

1.移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

---

方法1【暴力求解】

时间复杂度：O(N^2)

• 起始条件：遍历开始
• 中间过程：遍历数组中找到元素val，从后向前依次覆盖需要删除的元素val
• 结束条件：遍历数组完成

易错：

• 向前覆盖之后，循环变量一定要--，和数组元素个数也要--

int removeElement(int* nums, int numsSize, int val)
{
	int i = 0;
	for (i = 0; i < numsSize; i++)
	{
		if (nums[i] == val)
		{
			int j = i;
			while (j < numsSize)
			{
				nums[j] = nums[j + 1];
				j++;
			}
			numsSize--;
			i--;
		}
	}
	return numsSize;
}
//OJ上是错误的❌
//首先遍历数组一遍找到元素，从后向前依次覆盖需要删除的元素

---

方法2【双指针】

时间复杂度：O(N) 

• 起始条件：使用两个 下标dst src （其中dst存储不移除的元素，src遍历数组找到移除元素）
• 中间过程：num[src] 如果不是val，就将元素赋值给dst；如果是val,就src++ ，后面这个元素会被覆盖
• 结束条件：遍历数组完成

易错： 

• 返回的是修改之后的数组元素个数 dst  (画画图就可以理解了why?dst+1）

int removeElement(int* nums, int numsSize, int val)
{
    int src=0;
    int dst=0;
    while(src
    {
        if(nums[src] != val)
        {
            nums[dst++]=nums[src++];
        }
        else
        {
            src++;
        }
    }
    return dst;
}
//这里使用的是下标
//那指针呢？
//用辅助数组也可以，具体情况看题目要求

---

2.删除两个有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k 。
• 非严格递增排列 == 非递减排列  !=  乱序排列

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为1，2。不需要考虑数组中超出新长度后面的元素。

---

方法1【双指针】

  时间复杂度：O(N)

• 起始条件：使用两个 下标dst src （其中dst存储不移除的元素，src遍历数组找到移除元素）
• 中间过程：dst == src 相等的时候，不把元素放入dst中(无效位置后期可以覆盖），src++；dst != src不相等，把元素放入dst中。
• 结束条件：遍历数组完成

• 思想：不相等的放到src里面，相等就dst++，这样达到一个把相等的值覆盖的作用。相等的时候才会拉开差距，才有无效位置可以覆盖。

易错：

• 特别提醒：dst是下标，返回最后数组元素的时候需要+1 （对比上面）

int removeDuplicates(int* nums, int numsSize)
{
    int dst=1;
    int src=0;
    while(dst
    {
        if(nums[src] != nums[dst])
        {
            src++;
            nums[src]=nums[dst];
            dst++;
        }
        else
        {
            dst++;
//为什么这里src++移动到需要覆盖的位置，因为dst和src还要比较
//可以想下三指针怎么搞！
        }
    }
    return src+1;//易错
}
//数据下标
//指针呢？
//三个指针？
//用辅助数组也可以但是没必要

---

3.合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

---

方法1【暴力求解】

时间复杂度：O(N^2) 

• 起始条件 
• 中间过程：先合并在nums1，再冒泡排序
• 结束条件
• 这个方法效率低下：排序最快的 快速排序时间复杂度O(nlogN)

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int i=0;
    for(i=0;i
    {
        nums1[m+i]=nums2[i];
    }
 
    //排序
    for(i=0;i
    {
        int j=0;
        for(j=0;j-1-i;j++)
        {
            if(nums1[j]>nums1[j+1])
            {
                int tmp=nums1[j];
                nums1[j]=nums1[j+1];
                nums1[j+1]=tmp;
            }
        }
    }
 
}

---

方法2【开辟新数组】---选择较小的尾插 

 时间复杂度 O(N)

• 起始条件：设置三个下标p1 p2 j
• 中间过程：p1 p2 比较，较小的放到 j（指向新数组开头）里面， p1 p2正序遍历两个数组，最后拷贝回去。
• 结束条件：两个数组都遍历完成

易错： 

• 变长数组或动态内存开辟的数组空间 
• p1=m  p2=n   j=m+n
• 循环条件写的 j>0
• 循环条件p2>=0 || p1>=0
• 结束条件考虑周全p1< 0  或 p2 < 0的处理
• 循环条件里面是循环继续的条件

---

方法3【三指针】---选择较大的头插

时间复杂度 O(N)

• 起始条件：设置三个下标p1 p2 j
• 中间过程：p1 p2 比较，较大的放到 j（指向nums1的最后）里面， p1 p2倒叙遍历两个数组
• 结束条件：两个数组都遍历完成

易错：

• p1=m  p2=n   j=m+n
• 循环条件写的 j>0
• 循环条件p2>=0 || p1>=0
• 结束条件考虑周全p1< 0  或 p2 < 0的处理
• 循环条件里面是循环继续的条件

 
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int p1=m-1;
    int p2=n-1;//下标和元素个数的关系
    int j=m+n-1;
    while(p2>=0&&p1>=0)
    {
        if(nums1[p1]
        {
            nums1[j--]=nums2[p2];
            p2--;
        }
        else//p1>p2
        {
            nums1[j--]=nums1[p1];
            p1--;
        }
    }
    while(p2>=0)
    {
        nums1[j--]=nums2[p2--];
    }
}

 【整个思路】：

【详解】：

【结束条件】：

---

4.有序数组的合并

描述：输入两个升序排列的序列，将两个序列合并为一个有序序列并输出。
输入描述：输入包含三行，
第一行：包含两个正整数n, m，用空格分隔。n表示第二行第一个升序序列中数字的个数，m表示第三行第二个升序序列中数字的个数。
第二行：包含n个整数，用空格分隔。
第三行：包含m个整数，用空格分隔。
输出描述：
输出为一行，输出长度为n+m的升序序列，即长度为n的升序序列和长度为m的升序序列中的元素重新进行升序序列排列合并

示例1
输入： 5 6
            1 3 7 9 22
            2 8 10 17 33 44
输出： 1 2 3 7 8 9 10 17 22 33 44 

大家还记得这个题目吗？在我们数组题目当中也是讲解过暴力求解的方法。这里我们可以使用三指针的方法自己写一写。                    

      操作符&算数转换题_唐唐思的博客-CSDN博客                                                                           

方法1【三指针】 

---

✔✔✔✔✔最后，感谢大家的阅读，若有错误和不足，欢迎指正！ 

代码---------→【唐棣棣 (TSQXG) - Gitee.com】

联系---------→【邮箱：2784139418@qq.com】