349. Intersection of Two Arrays

刺骨的言语ヽ痛彻心扉 2022-04-25 03:22 84阅读 0赞

Given two arrays, write a function to compute their intersection.

**Example 1:**

Input: nums1 = [1,2,2,1], nums2 = [2,2]
    Output: [2]

**Example 2:**

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    Output: [9,4]

**Note:**

*  Each element in the result must be unique.
 *  The result can be in any order.

解题思路：思路一，python的集合有一个求交集的方法

思路二，将两个数组按照从小到大排序，然后遍历，挨个比较，一样的情况下，再判断是否在新数组，不在的情况下加入到新数组；

python代码：

class Solution:
        def intersection(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: List[int]
            """
            l1 = len(nums1)
            l2 = len(nums2)
            res = set()
            if l1 <= l2:
                s = nums1
                l = nums2
            else:
                l = nums1
                s = nums2
            for i in l:
                if i in s:
                    res.add(i)
            return list(res)

C语言代码：

/**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    
    int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
        int i,j,k=0,flag=0;
        int lens=nums1Size>nums2Size?nums1Size:nums2Size;
        int* re =(int*)malloc(sizeof(int)*lens);
        if(nums1Size==0) { * returnSize=k; return nums1; }
        if(nums2Size==0) { * returnSize=k; return nums2; }
     for(i=0;i<nums1Size;i++)
        {//flag用来标识数组re中是否已经存在nums1和nums2的交集，flag==0，则只要比较nums2[j]==nums1[i]
        if(flag==0)
             for(j=0;j<nums2Size;j++)
               { if(nums2[j]==nums1[i]) 
                   {flag=1;re[k++]=nums1[i];break;} 
               }      
    //flag==1说明re中已存在交集数字，则nums1[i]还需要与re数组中的每个元素进行比较，保证输出结果中的每个元素一定是唯一的           
        else if(flag==1)
         {int t,f=0;
                   for (t=0;t<k;t++) 
                       if(nums1[i]==re[t]) { f=1;break;}
           if(f==1) continue;//一开始写成了break
              for(j=0;j<nums2Size;j++)    
                {
                  if(nums2[j]==nums1[i]) 
                  { flag=1;re[k++]=nums1[i];break;}
                }        
           }
        }   
        * returnSize=k;
        return re;
    
    }