0

我试图解决以下问题：给定两个整数数组 nums1 和 nums2，返回它们的交集数组。结果中的每个元素必须出现在两个数组中的次数，并且您可以按任意顺序返回结果。

示例 1：输入：nums1 = [1,2,2,1]，nums2 = [2,2] 输出：[2,2]

这是我的代码：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    
    for(int i=0; i<nums1Size-1; i++){
        if(nums1[i]>nums1[i+1]){
            int temp = nums1[i];
            nums1[i] = nums1[i+1];
            nums1[i+1] = temp;
            i = -1;
        }
    }
    
    for(int i=0; i<nums2Size-1; i++){
        if(nums2[i]>nums2[i+1]){
            int temp = nums2[i];
            nums2[i] = nums2[i+1];
            nums2[i+1] = temp;
            i = -1;
        }
    }
    
    int i = 0;
    int j = 0;
    int* res = (int*)malloc(10* sizeof(int));
    int k = 0;
    
    if(!(nums1Size > nums2Size)){
        int * temp = nums1;
        nums1 = nums2;
        nums2 = temp;
        int tempint = nums1Size;
        nums1Size = nums2Size;
        nums2Size = tempint;
    }
    
    while(i<nums1Size && j<nums2Size){
        if(nums1[i] > nums2[j]){
            j++;
        }
        else if(nums1[i] < nums2[j]){
            i++;
        }
        else{
            res[k++] = nums1[i];
            i++; j++;
        }
    }
    *returnSize = sizeof(res)/sizeof(res[0]);
    return res;

}
4

1 回答 1

0

为了简化您必须解决的问题，让我们首先编写一个辅助函数来计算数组中特定元素的出现次数：

int count_elem(int* arr, int n, int elem) {
    int count = 0;

    for (int i = 0; i < n; i += 1) {
        if (arr[i] == elem) {
            count += 1;
        }
    }

    return count;
}

现在，让我们尝试按照问题描述解决问题：

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    // here we allocate `res` with size of the biggest array, because that's the worst case we'll have
    int* res = malloc(sizeof(int) * ((nums1Size > nums2Size) ? nums1Size : nums2Size));

    // just to be sure `malloc()` did not return an error
    if (res == NULL) {
        return NULL;
    }

    // we'll keep track of how many elements we actually put inside `res`
    *returnSize = 0;

    // let's loop through all elements of `nums1`
    for (int i = 0; i < nums1Size; i += 1) {
        int elem = nums1[i];

        // if we already put the element inside `res`, we skip this cycle
        int count_res = count_elem(res, *returnSize, elem);
        if (count_res > 0) {
            continue;
        }

        // let's count the occurrences in both arrays
        int count1 = count_elem(nums1, nums1Size, elem);
        int count2 = count_elem(nums2, nums2Size, elem);

        // let's calculate how many times the element must be present inside `res`
        // i.e.: the same number of times of the array with the fewer occurrences of it
        // NOTE: if `nums1` or `nums2` do not include the element, we also don't include it inside `res`
        int count_min = (count1 < count2) ? count1 : count2;

        // now let's put inside `res` as many times as we previously calculated
        for (int i = 0; i < count_min; i += 1) {
            res[*returnSize] = elem;
            *returnSize += 1;
        }
    }

    return res;
}

让我们试试它是否有效：

int main(void) {
    int arr1[] = {1, 2, 2, 1};
    int arr2[] = {2, 2};

    int res_size;
    int* res = intersect(arr1, sizeof(arr1) / sizeof(arr1[0]), arr2, sizeof(arr2) / sizeof(arr2[0]), &res_size);

    // let's print the result of `intersect()`
    for (int i = 0; i < res_size; i += 1) {
        printf("%d\n", res[i]);
    }

    return 0;
}

输出：

2
2

注意：该功能没有针对速度和内存效率进行优化。这将作为练习留给读者。

更新

以前版本的答案是错误的（再次抱歉）。现在应该是正确的。

于 2021-09-21T17:25:04.773 回答