leetcode 349. 两个数组的交集 两种方案，c语言实现

如题：

给定两个数组，编写一个函数来计算它们的交集。

示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

属于简单类型，两种方案。

方案一：是使用hash，不过c语言里面没有内置hash结构，需要手动实现，很多c方案采用此方法，不过没有考虑到负数问题，都是拿到数组后使用hash[nums[i]] 计算，这里nums[i]可能是负数。假设数组分别位A、B。将其中任意一个数组元素装入hash桶中，然后比较另一个数组即可。

方案二：先将俩数组排序，排好序后去重。最后比较俩有序数组，取出相同元素即可。简单快捷。代码如下：

/**
 * 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\n", nums1Size, nums2Size);
    //去重
    deduplicate(nums1, &nums1Size);
    deduplicate(nums2, &nums2Size);
    printf("A size:%d, B size:%d\n", 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)，对后端、互联网感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。