【数据结构刷题】数组oj

前言:
	本文章是关于在力扣上面的数组相关面试题的讲解，包括:
	1.原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1),
	2.删除排序数组中的重复项。
	3. 合并两个有序数组。

一.原地移除数组中所有的元素val

题目:
https://leetcode.cn/problems/remove-element/

1.1时间复杂度为O(N^2)，空间复杂度为O(1)

写一段原地移除数组中所有的元素val，要求时间复杂度为O(N^2)，空间复杂度为O(1)的代码实现:
思路:遇到这个val后面的元素往前面覆盖。

  int removeElement(int* nums, int numsSize, int val) {
    int i, j;
    int newSize = numsSize;

    for (i = 0; i < newSize; i++) {
        if (nums[i] == val) {
            for (j = i; j < newSize - 1; j++) {
                nums[j] = nums[j + 1];
            }
            newSize--;
            i--; // 重复检查当前位置
        }
    }

    return newSize; } 

int main() {
int nums[] = { 0, 1, 2, 2, 3, 0, 4, 2 };
int numsSize = sizeof(nums) / sizeof(nums[0]);
int val = 2;

int newSize = removeElement(nums, numsSize, val);

printf("修改后的数组: ");
for (int i = 0; i < newSize; i++) {
    printf("%d ", nums[i]);
}

return 0; } 

1.2时间复杂度为O(N)，空间复杂度为O(N)

写一段原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(N)的代码实现:
思路:

#include <stdlib.h> int* removeElements(int* nums, int numsSize, int val, int* newSize) {
     int i, j;
    		 int* tmp = (int*)malloc(numsSize * sizeof(int)); // 创建一个临时数组
     int count = 0; // 计数器，记录移除元素后的数组长度
   	  for (i = 0; i < numsSize; i++) {
         if (nums[i] != val) {
             tmp[count] = nums[i]; // 将非 val 元素保存到临时数组
             count++;
         }
     }
 
    *newSize = count; // 更新新数组的长度
 
    return tmp; // 返回临时数组的指针
     }

int main() {
    int nums[] = { 0, 1, 2, 2, 3, 0, 4, 2 };
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int val = 2;

    int newSize;
    int* newArray = removeElements(nums, numsSize, val, &newSize);

    printf("移除元素后的数组: ");
    for (int i = 0; i < newSize; i++) {
        printf("%d ", newArray[i]);
    }
    printf("\n新长度: %d\n", newSize);

    free(newArray); // 释放临时数组的内存

    return 0; } ```

1.3符合此题的正确写法:

原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1):

写法2与这篇文章的唯一的区别是本文章需要return j，其余部分一样，而写法1的大致思路画图思路相差不大，就不用动图演示了,传送门–>序列中删除指定数字,有动图演示
图解:

#include<stdio.h>
/写法一
int removeElement(int *nums,int numsSize,int val)
{
	int src = 0;
	int dst = 0;
	while (src < numsSize)
	{
		if (nums[src] != val)
		{
			nums[dst++] = nums[src++];
		}
		else
		{
			src++;
		}
	}
	return dst;
}
//写法二
int removeElement(int* nums, int numsSize, int val){
      int i=0;
      int j=0;
      for(i=0;i<numsSize;i++)
      {
       if(nums[i]!=val)
      {
        nums[j++]=nums[i];
      }
      }
        return j;
}

int main() {
int nums[] = { 0, 1, 2, 2, 3, 0, 4, 2 };
int sz =sizeof(nums) / sizeof(nums[0]);
int val = 2;
int ret=removeElement(nums, sz, val);
printf(“%d”,ret);
}

二. 删除排序数组中的重复项。

题目:
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

动图演示:

#include<stdio.h>
int removeDuplicates(int* nums, int numsSize) {
	int src = 1, dst = 0;
	while (src < numsSize)
	{
		if (nums[src] != nums[dst])
		{
			nums[++dst] = nums[src++];
		}
		else
		{
			src++;
		}
	}
	return dst+1;//因为dst是下标，所以要+1
}

int main()
{
	int nums[] = { 0,0,1,1,1,2,2,3,3,4 };
	int sz = sizeof(nums) / sizeof(nums[0]);
	int ret=removeDuplicates(nums, sz);
	printf("%d", ret);
}

执行：

三. 合并两个有序数组

题目:
https://leetcode.cn/problems/merge-sorted-array/

思路:无论是下面哪种情况，nums1数组都是目标数组，都是长的那个。
要是end2先结束，那就不用拷贝到目标数组nums1，直接打印nums1即可
若是end1先结束，需要先把nums2(短数组的元素)拷贝到nums1，再打印

3.1end1>0，end2<0

3.2end1<0,end2>0

代码实现:

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
       int end1=m-1;
       int end2=n-1;
       int i=m+n-1;
    while(end1>= 0&& end2>=0)
    {    
    if(nums1[end1]>nums2[end2])
      {
        nums1[i--]=nums1[end1--];
      }        
      else
      {
          nums1[i--]=nums2[end2--];
      }
    }
    while(end2>=0)
    {
    nums1[i--]=nums2[end2--];
    }
    
}

执行:

文章到这就写完了，如有错误欢迎指正，谢谢！