leetcode 349. 2つの配列の交差の2つのスキーム、c言語の実現
3088 ワード
問題:
単純なタイプ、2つのシナリオに属します.
シナリオ1:hashを使用しますが、c言語にはhash構造が内蔵されておらず、手動で実現する必要があります.多くのcシナリオではこの方法が採用されていますが、負数の問題は考慮されていません.配列を手に入れた後にhash[nums[i]]を使用して計算されます.ここでnums[i]は負数かもしれません.配列それぞれのビットA,Bを仮定する.いずれかの配列要素をhashバケツに入れ、別の配列を比較すればよい.
シナリオ2:まず2つの配列を並べ替えて、順番を並べてから重くします.最後に2つの秩序配列を比較し,同じ要素を取り出せばよい.簡単で速い.コードは次のとおりです.
=============================================================================================
Linuxアプリケーション、カーネル、駆動開発交流討論群(745510310)、バックエンド、インターネットに興味のある学生はグループ討論、交流、資料検索などを加えることができて、前進する道の上で、あなたは一人ではありません^^.
, 。
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)、バックエンド、インターネットに興味のある学生はグループ討論、交流、資料検索などを加えることができて、前進する道の上で、あなたは一人ではありません^^.