leetcode 349. 2つの配列の交差の2つのスキーム、c言語の実現

問題:

      ，              。

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

   2:
  : nums1 = [4,9,5], nums2 = [9,4,9,8,4]
  : [9,4]

  :
                。
              。

単純なタイプ、2つのシナリオに属します.
シナリオ1:hashを使用しますが、c言語にはhash構造が内蔵されておらず、手動で実現する必要があります.多くのcシナリオではこの方法が採用されていますが、負数の問題は考慮されていません.配列を手に入れた後にhash[nums[i]]を使用して計算されます.ここでnums[i]は負数かもしれません.配列それぞれのビットA,Bを仮定する.いずれかの配列要素をhashバケツに入れ、別の配列を比較すればよい.
シナリオ2:まず2つの配列を並べ替えて、順番を並べてから重くします.最後に2つの秩序配列を比較し,同じ要素を取り出せばよい.簡単で速い.コードは次のとおりです.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//  1：    hash ，       ，          
//  2：         ，         ，      
#define MAX(a,b) ((a) > (b) ? (a):(b))

//    
void swap(int *a, int *b)
{
    if (a == b)
        return;
	*a = *a ^ *b;
	*b = *a ^ *b;
	*a = *a ^ *b;
    return;
}

//    
void quickSort(int *arr, int low, int high)
{
	int pivotKey, pivotLoc;
	int left = low;
	int right = high;
	if (low < high)
	{
		//         
		pivotLoc = (low + high) / 2;
		pivotKey = arr[pivotLoc];
		while (low < high)
		{
			while (low < pivotLoc && arr[low] <= pivotKey)low++;
			if (low < pivotLoc)
			{
				swap(arr+low, arr+pivotLoc);
				pivotLoc = low;
			}
			
			while(high > pivotLoc && arr[high] >= pivotKey)high--;
			if (high > pivotLoc)
			{
				swap(arr+high, arr+pivotLoc);
				pivotLoc = high;					
			}
		}
 
		quickSort (arr, left, pivotLoc);
		quickSort (arr, pivotLoc + 1, right);
	}
	return;
}

//  
void deduplicate(int *nums, int *numsSize)
{
    int i, j, len = *numsSize;
    for (i = 0, j = 1; j < len; j++)
    {
        if (nums[j] == nums[i])
            *numsSize = *numsSize - 1;
        else
        {
            swap(nums+i+1, nums+j);
            i++;
        }        
    }
    return;
}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    
    int i,j,k,len, *ret;
    len = MAX(nums1Size, nums2Size);
    if (len <= 0) len = 1;
    
    ret = (int *)calloc(len, sizeof(int));
    *returnSize = 0;
    
    //      
    if (!nums1|| nums1Size < 0 || !nums2 || nums2Size < 0)
        return ret;
    
    //  
    quickSort(nums1,0,nums1Size-1);
    quickSort(nums2,0,nums2Size-1);
    printf("A size:%d, B size:%d
", nums1Size, nums2Size);
    //  
    deduplicate(nums1, &nums1Size);
    deduplicate(nums2, &nums2Size);
    printf("A size:%d, B size:%d
", nums1Size, nums2Size);
    
    //  
    for (i = 0, j = 0, k = 0; i < nums1Size && j < nums2Size;)
    {
        if (nums1[i] == nums2[j])
        {
            ret[k] = nums1[i];
            i++;j++;k++;
        }
        else if (nums1[i] < nums2[j])
            i++;
        else
            j++;
    }
    
    *returnSize = k;
    return ret;
}

=============================================================================================
Linuxアプリケーション、カーネル、駆動開発交流討論群(745510310)、バックエンド、インターネットに興味のある学生はグループ討論、交流、資料検索などを加えることができて、前進する道の上で、あなたは一人ではありません^^.