[LeetCode]349. Intersection of Two Arrays ★

毎日1本のプログラミングの問題

タイトル説明

サンプル

python解法

C言語解法

タイトルの説明
Given two arrays, write a function to compute their intersection. 2つの与えられた集合の交差を求めます
サンプル
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]
python解法

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        s = set1.intersection(set2)
        return list(s)

Runtime: 52 ms, faster than 84.32% of Python3 online submissions for Intersection of Two Arrays. Memory Usage: 14 MB, less than 5.88% of Python3 online submissions for Intersection of Two Arrays. 問題後の反省:なし
C言語解法

struct linklist{
    int val;
    struct linklist *next;
};

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int location(int *num, int len, int com)
{
    for (int i=0;i<len;i++)
    {
        if (num[i] == com)
            return i;
    }
    return -1;
}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    if (!nums1Size || !nums2Size)
    {
        *returnSize=0;
        return NULL;
    }
    struct linklist *num[nums2Size];
    for(int i=0;i<nums2Size;i++)
        num[i] = NULL;
    int remain = 0;
    struct linklist *link = NULL;
    for(int i=0;i<nums2Size;i++)
    {
        remain = nums2[i]%nums2Size;
        link = (struct linklist *)malloc(sizeof(struct linklist));
        link -> val = nums2[i];
        link -> next = num[remain];
        num[remain] = link;
    }
    int *returnValue = NULL;
    *returnSize = 0;
    for (int i=0;i<nums1Size;i++)
    {
        remain = nums1[i]%nums2Size;
        link = num[remain];
        while(link)
        {
            if(link -> val == nums1[i])
            {
                if (location(returnValue, *returnSize, nums1[i]) == -1)
                {
                    returnValue = (struct linklist*)realloc(returnValue, sizeof(int)*(*returnSize + 1));
                    returnValue[*returnSize] = nums1[i];
                    (*returnSize) ++;
                    break;
                }
            }
            link = link->next;
        }
    }
    return returnValue;
}

Runtime: 4 ms, faster than 94.02% of C online submissions for Intersection of Two Arrays. Memory Usage: 8.8 MB, less than 100.00% of C online submissions for Intersection of Two Arrays. 問題後の反省:

は、配列検索が遅いという問題を解決するためにハッシュテーブルを使用する.

C言語には対応するデータ構造がなく,自分で実現するコードが明らかに多い.

文の中ですべて私個人の理解で、もし間違いがある地方は下の評論が私に教えてくれることを歓迎して、私は直ちに訂正して、みんなは共に進歩します