[349] Intersection of Two Arrays

是不是一個用C++很簡單的題目Orz

奇怪晚上思考能力好差～到底在寫什麼Orz

明天再來寫個hash的版本吧(?)

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int comp(const void *a, const void *b)

{

return (*(int*)a-*(int*)b);

}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {

qsort(nums1,nums1Size,sizeof(int),comp);

qsort(nums2, nums2Size, sizeof(int),comp);

int idx1=0, idx2=0;

int *ret = calloc (nums1Size,sizeof(int)*(nums1Size));

int retIdx=0;

while (idx1< nums1Size && idx2 < nums2Size)

{

if (nums1[idx1]==nums2[idx2])

{

int item = nums1[idx1];

ret[retIdx++]= item;

while (idx1<nums1Size && nums1[idx1]==item)

idx1++;

while (idx2<nums2Size && nums2[idx2]==item)

idx2++;

}

else if (nums1[idx1] < nums2[idx2])

idx1++;

else

idx2++;

}

*returnSize = retIdx;

return ret;

}

Update XD has 版本來惹～

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {

int *hash1= calloc(1001, sizeof(int)*1001);

int retIdx=0;

int *ret= calloc(1001, sizeof(int)*1001);

for (int i=0;i<nums1Size;i++)

hash1[nums1[i]]++;

for (int i=0; i<nums2Size;i++)

{

if (hash1[nums2[i]]>0)

{

hash1[nums2[i]]=0;

ret[retIdx++]= nums2[i];

}

}

*returnSize = retIdx;

return ret;

}