给定两个数组，写一个方法来计算它们的交集。
例如:
给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].
注意：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
跟进:
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？
思路1
一个个遍历，遇到相同的数，将其加入集合，将这个数与数组最后一位交换，该数组的长度减一
实现代码
C语言
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int k=0;
int *result=(int *)malloc(nums2Size*sizeof(int));
for(int i=0;i<nums1Size;++i){
for(int j=0;j<nums2Size;++j){
if(nums1[i]==nums2[j]){
if(nums2Size>0){
result[(*returnSize)++]=nums1[i];
int temp=nums2[j];
nums2[j]=nums2[nums2Size-1];
nums2[nums2Size-1]=temp;
nums2Size--;
}
break;
}
}
}
return result;
}
实现代码
Java
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
int returnSize[];
List<Integer> list=new ArrayList<Integer>();
int nums2Size=nums2.length;
for(int i=0;i<nums1.length;++i){
for(int j=0;j<nums2Size;++j){
if(nums1[i]==nums2[j]){
if(nums2Size>0){
list.add(nums1[i]);
int temp=nums2[j];
nums2[j]=nums2[nums2Size-1];
nums2[nums2Size-1]=temp;
nums2Size--;
}
break;
}
}
}
int[] result = new int[list.size()];
int i = 0;
for (Integer e : list)
result[i++] = e;
return result;
}
}
思路2
用HashMap存储第一个数组，key为数组的值，value为该值出现次数，然后用该map去遍历第二个数组，如果查到有这个键，则将该键放到list，值减一
实现代码
HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0;i<nums1.length;++i) {
if(map.containsKey(nums1[i])) {
map.put(nums1[i], map.get(nums1[i])+1);
}else {
map.put(nums1[i], 1);
}
}
for(int i=0;i<nums2.length;++i) {
if(map.containsKey(nums2[i])&&map.get(nums2[i])>0) {
list.add(nums2[i]);
map.put(nums2[i], map.get(nums2[i])-1);
}else {
}
}
int[] result=new int[list.size()];
for(int i=0;i<list.size();++i) {
result[i]=list.get(i);
}
return result;
}
思路3
对两个数组进行排序，然后对两个数组进行比较，小的一方下标加1，相等时两个数组下标都加1。
实现代码
Java
Arrays.sort(nums1);
Arrays.sort(nums2);
ArrayList<Integer> list = new ArrayList<Integer>();
int i=0,j=0;
while(i<nums1.length&&j<nums2.length){
if(nums1[i]==nums2[j]){
list.add(nums1[i]);
++i;
++j;
}
else if(nums1[i]>nums2[j]){
++j;
}
else{
++i;
}
}
int[] result=new int[list.size()];
for(int k=0;k<list.size();++k) {
result[k]=list.get(k);
}
return result;
C语言
int partition(int arr[], int low, int high){
int key;
key = arr[low];
while(low<high){
while(low <high && arr[high]>= key )
high--;
if(low<high)
arr[low++] = arr[high];
while( low<high && arr[low]<=key )
low++;
if(low<high)
arr[high--] = arr[low];
}
arr[low] = key;
return low;
}
void quick_sort(int arr[], int start, int end){
int pos;
if (start<end){
pos = partition(arr, start, end);
quick_sort(arr,start,pos-1);
quick_sort(arr,pos+1,end);
}
}
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
quick_sort(nums1,0,nums1Size-1);
quick_sort(nums2,0,nums2Size-1);
int size = nums1Size<nums2Size?nums1Size:nums2Size;
int *result=(int *)malloc(size*sizeof(int));
//memset(result,0,sizeof(int)*size);
int i=0,j=0,z=0;
while(i<nums1Size&&j<nums2Size){
if(nums1[i]==nums2[j]){
result[z]=nums1[i];
++i;
++j;
++z;
}
else if(nums1[i]>nums2[j]){
++j;
}
else {
++i;
}
}
*returnSize=z;
return result;
}
