算法OJ题（1）

灰太狼 2023-09-26 23:54 65阅读 0赞

**1.删除有序数组中的重复项**

**[原题链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/][https_leetcode.cn_problems_remove-duplicates-from-sorted-array]**

![05c869d964474214830c8fd6da4fa9b1.png][]

![250cf302b6d5420b909317c49aab01e8.png][]

思路：使用双指针算法可以使时间复杂度达到O(1).

**具体过程：（以画图解释）**

![ba99d077b17a4dc3ad80a4b049621fdd.png][]

![aea7659071504eec9b8655bf3e39de08.png][]

代码实现：

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;
    }

**2.合并两个有序数组**

**原题链接：[https://leetcode.cn/problems/merge-sorted-array/][https_leetcode.cn_problems_merge-sorted-array]**![594dc53478fd4b939999f7590759c219.png][]

![8b9b2e6d5a4341afa03570a5c7324399.png][]

思路：双指针算法

实现过程：

定义两个变量end1，end2 ，分别指向两个数组的最后一个元素

比较num1\[end1\]和num2\[end2\]的大小，将较大值依次移到数组一，从后往前进行

如下图：

![0515df96a9de45aaa11fc73c1f589a5d.png][]

代码实现：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
    {
        int end1=m-1,end2=n-1;
        int end=m+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--];
        }
    }

[https_leetcode.cn_problems_remove-duplicates-from-sorted-array]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
[05c869d964474214830c8fd6da4fa9b1.png]: https://img-blog.csdnimg.cn/05c869d964474214830c8fd6da4fa9b1.png
[250cf302b6d5420b909317c49aab01e8.png]: https://img-blog.csdnimg.cn/250cf302b6d5420b909317c49aab01e8.png
[ba99d077b17a4dc3ad80a4b049621fdd.png]: https://img-blog.csdnimg.cn/ba99d077b17a4dc3ad80a4b049621fdd.png
[aea7659071504eec9b8655bf3e39de08.png]: https://img-blog.csdnimg.cn/aea7659071504eec9b8655bf3e39de08.png
[https_leetcode.cn_problems_merge-sorted-array]: https://leetcode.cn/problems/merge-sorted-array/
[594dc53478fd4b939999f7590759c219.png]: https://img-blog.csdnimg.cn/594dc53478fd4b939999f7590759c219.png
[8b9b2e6d5a4341afa03570a5c7324399.png]: https://img-blog.csdnimg.cn/8b9b2e6d5a4341afa03570a5c7324399.png
[0515df96a9de45aaa11fc73c1f589a5d.png]: https://img-blog.csdnimg.cn/0515df96a9de45aaa11fc73c1f589a5d.png