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)、バックエンド、インターネットに興味のある学生はグループ討論、交流、資料検索などを加えることができて、前進する道の上で、あなたは一人ではありません^^.