leetcode:两个数组的交集(双指针)

链接:力扣

题意:

leetcode:两个数组的交集(双指针)

注:交集的元素是唯一的,不能重复

我的题解:(完整代码在最下面)


int cmp(const void* e1,const int* e2)
{
    return (*(int*)e1-*(int*)e2);
}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
    int i=0,j=0;            //分别指向nums1和nums2数组
    int k=0,cur=0;          //k专门用于记录符合题意的数组ans的下标
    int len = (nums1Size>nums2Size)? nums2Size : nums1Size;   //算出较短的数组的长度
    int* ans=(int*)malloc(len*sizeof(int));         //题解极端的情况就是和比较小的数组一致
    qsort(nums1,nums1Size,sizeof(nums1[0]),cmp);    //快排
    qsort(nums2,nums2Size,sizeof(nums2[0]),cmp);
    cur=nums1[i]-1;       //这里的cur保证同种数字只有一个数字在ans数组里面
    // ↑ 这里随便赋值就行,只要让他不属于其中一个数组里面的元素就行
}

 循环体:


    while(i<nums1Size && j<nums2Size)
    {
        if(nums1[i]>nums2[j])            //如果nums1[i]比较大,那j指针右移,下面同理
        {
            j++;
        }
        else if(nums1[i]<nums2[j])
        {
            i++;
        }
        else if(nums1[i]==nums2[j] && cur!=nums1[i])   //防止同种元素进入ans
        {
            ans[k++]=nums1[i];
            cur=nums1[i];                              //记录这个元素
            i++;
            j++;
        }
        else
        {
            i++;                            //这里换成j++也没有问题
        }
    }

完整代码:


int cmp(const void* e1,const int* e2)
{
    return (*(int*)e1-*(int*)e2);
}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
    int i=0,j=0,k=0,cur=0;
    int len = (nums1Size>nums2Size)? nums2Size : nums1Size;
    int* ans=(int*)malloc(len*sizeof(int));
    qsort(nums1,nums1Size,sizeof(nums1[0]),cmp);
    qsort(nums2,nums2Size,sizeof(nums2[0]),cmp);
    cur=nums1[i]-1;
    while(i<nums1Size && j<nums2Size)
    {
        if(nums1[i]>nums2[j])
        {
            j++;
        }
        else if(nums1[i]<nums2[j])
        {
            i++;
        }
        else if(nums1[i]==nums2[j] && cur!=nums1[i])
        {
            ans[k++]=nums1[i];
            cur=nums1[i];
            i++;
            j++;
        }
        else
        {
            i++;
        }
    }
    *returnSize=k;
    return ans;
}

上一篇:【笔记】C语言学习笔记02


下一篇:[C++] vptr, where are you?