【LeetCode刷题集】--排序（二）

用户11915063

发布于 2025-11-20 09:18:16

640

题目一：合并两个有序数组

题目链接：

88.合并两个有序数组-力扣（LeetCode）

题意：

给了两个非递减顺序数组，m和n分别代表nums1和nums2的元素数目，合并nums1和nums2数组，并且使之合并为非递减顺序排列

思路：

因为是两个非递减顺序数组，这里就不需要我们自己排序了，这里我们知道m和n，此时就可以得出合并后数组的元素个数为m+n，首先取nums1数组最后一位下标l1=m-1，nums2数组最后一位下标l2=n-1，合并后数组最后一位下标m+n-1,接着我们让nums1和nums2从最后开始遍历，大的放到最后一位，此时再让下标--即可，若最后数组还剩有元素没有放完，在将没放完数组全部放进去即可，因为我们是非递减顺序数组，越往前数组的元素肯定越小

代码实现：

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

复杂度分析：

时间复杂度：O(M+N) 注：但是复杂度不是这样写的，最后写成O(N) 这里如果大家对算法复杂度不清楚的话，大家可以参考下我的这篇博客，里面详细讲解了计算算法复杂度的规则：【数据结构初阶】--算法复杂度详解

题目二：丢失的数字

题目链接：

268.丢失的数字-力扣（LeetCode）

题意：

给了一个[0，n]的数组，找出没有出现在这个范围内的数字

思路：

我们可以将数组先排好序，因为排好序的数组，数组下标和数字是一一对应的，此时我们只要找出来数组下标与数组元素不相同的元素，返回数组下标即可

代码实现：

int cmp(const void*a,const void*b)
{
    return *(int*)a-*(int*)b;
}
int missingNumber(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(nums[0]),cmp);
    int i=0;
    while(i<numsSize)
    {
        if(nums[i]==i)
        {
            ++i;
        }
        else
            break;
    }
    return i;
}

复杂度分析：

时间复杂度：Nlogn

题目三：找不同

题目链接：

389.找不同-力扣（LeetCode）

题意：

有两个字符串s和t，在字符串t中添加一个字母，找出添加的字母即可

思路：

我们可以将字符串s和字符串t进行排序，让s和t中的字符全部相加，s和t的差值就是添加的字符

代码实现：

char findTheDifference(char* s, char* t) 
{
    int snum=strlen(s),tnum=strlen(t);
    int scount=0,tcount=0;
    for(int i=0;i<snum;i++)
    {
        scount+=s[i];
    }
    for(int i=0;i<tnum;i++)
    {
        tcount+=t[i];
    }
    return tcount-scount;
}