Leetcode算法題（C語言）7--兩個數組的交集 II

題目：兩個數組的交集 II

給定兩個數組，編寫一個函數來計算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]

輸出: [2,2]

示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

輸出: [4,9]

說明：

輸出結果中每個元素出現的次數，應與元素在兩個數組中出現的次數一緻。

我們可以不考慮輸出結果的順序。

代碼實作：

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

int Partition(int A[], int left, int right)  // 劃分函數
{
    int pivot = A[right];               // 這裡每次都選擇最後一個元素作為基準
    int tail = left - 1;                // tail為小于基準的子數組最後一個元素的索引
    for (int i = left; i < right; i++)  // 周遊基準以外的其他元素
    {
        if (A[i] <= pivot)              // 把小于等于基準的元素放到前一個子數組末尾
        {
            Swap(A, ++tail, i);
        }
    }
    Swap(A, tail + 1, right);           // 最後把基準放到前一個子數組的後邊，剩下的子數組既是大于基準的子數組
                                        // 該操作很有可能把後面元素的穩定性打亂，是以快速排序是不穩定的排序算法
    return tail + 1;                    // 傳回基準的索引
}

void QuickSort(int A[], int left, int right)
{
    if (left >= right)
        return;
    int pivot_index = Partition(A, left, right); // 基準的索引
    QuickSort(A, left, pivot_index - 1);
    QuickSort(A, pivot_index + 1, right);
}

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    
    int len = nums2Size;
    int i, j, k = 0;
    int flag = 0;
    int *array_bak;
    
    /* 快速排序 */
    QuickSort(nums1, 0, nums1Size - 1);
    QuickSort(nums2, 0, nums2Size - 1);
    
    /* 處理特殊情況并擷取數組長度 */
    if(nums1Size == 0)
        return;
    else if(nums2Size == 0)
        return;
    else if(nums1Size < nums2Size)
        len = nums1Size;
    
    int array[len];
    
    /* 判斷數組中是否有交集 */
    for(i = 0; i < nums1Size; i++)
    {
        for(j = flag; j < nums2Size; j++)
        {
            if(nums1[i] == nums2[j])
            {
                array[k] = nums2[j];
                k++;
                flag = j + 1;
                break;
            }
        }
    }
    /* 傳回數組大小 */
    *returnSize = k;
    /* 為傳回數組配置設定空間 */
    array_bak = (int *)malloc(sizeof(int) * k);
    /* 為傳回數組指派 */
    memcpy(array_bak, array, sizeof(int) * k);
    return array_bak;
}