【C语言】LeetCode26.删除有序数组中的重复项＆＆LeetCode88.合并两个有序数组

目录

删除有序数组中的重复项

合并两个有序数组

结语

---

描述：

给你一个升序排列的数组nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持一致 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例1

输入：

nums = [1,1,2]

输出：

2, nums = [1,2,_]

解释：

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

示例2

输入：

nums = [0,0,1,1,1,2,2,3,3,4]

输出：

5, nums = [0,1,2,3,4]

解释：

函数应该返回新的长度5 ，并且原数组nums的前五个元素被修改为0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

思路一：

int removeDuplicates(int* nums, int numsSize){

    if (numsSize == 0)
        return 0;
    int i = 0, j = 1;
    int dst = 0;
    while (j < numsSize)
    {

        if (nums[i] == nums[j])
        {
            j++;
        }
        else
        {
            nums[dst] = nums[i];
            dst++;
            i = j;
            j++;
        }
    }
    nums[dst] = nums[i];
    dst++;
    return dst;
}

思路二：

int removeDuplicates(int* nums, int numsSize) 
{
    if (numsSize == 0) 
        return 0;
    int fast = 1, slow = 1;
    while (fast < numsSize) 
    {
        if (nums[fast] != nums[fast - 1]) 
        {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++fast;
    }
    return slow;
}

  分析：时间复杂度为O(N)，空间复杂度为O(1)。

合并两个有序数组

说明：

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

注意：

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

示例

输入：

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] 。

进阶：

你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

思路一：

  最简单直观的方法就是，先将数组nums2放进数组nums1的尾部，然后再对数组num1进行快速排序。

int cmp(int* a, int* b)
{
	return *a - *b;
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
	for (int i = 0; i < n; i++)
	{
		nums1[m + i] = nums2[i];
	}
	qsort(nums1, m + n, sizeof(int), cmp);
}

  分析：时间复杂度：O((m+n)log(m+n))，空间复杂度：O(log(m+n)。

思路二：

  开辟一个新的数组，先将小的元素存放进去。当其中一个数组的元素存放完，再将另一个数组的元素存放进去，最后将该数组的数据拷贝给目标数组。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	int i = 0, j = 0, k = 0;
	int* nums = (int*)malloc(sizeof(int) * (m + n));
	//i为nums的下标，j为nums1的下标，k为nums2的下标
	while (j < m && k < n)
	{
		if (nums1[j] < nums2[k])
		{
			nums[i] = nums1[j];
			i++;
			j++;
		}
		else
		{
			nums[i] = nums2[k];
			i++;
			k++;
		}
	}
	while (j < m)
	{
		nums[i] = nums1[j];
		i++;
		j++;
	}
	while (k < n)
	{
		nums[i] = nums2[k];
		i++;
		k++;
	}
	memcpy(nums1, nums, sizeof(int) * (m + n));
}

  分析：时间复杂度为O(m+n)，空间复杂度为O(m+n)。

思路三：

  不开辟额外的空间，直接先将较大的元素存放到数组nums的后面，直到其中一个数组存放完。如果数组nums1先存放完，那么数组nums2中还有元素需要存放到数组nums1的前面；如果数组nums2先存放完，那么现在的数组num1就是所求的数组。

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

 

  分析：时间复杂度为O(m+n)，空间复杂度为O(m+n)，这是这道题最优的解法。 

结语

  每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根。