349. 两个数组的交集
349. 两个数组的交集
分析
简单说一下思路。
因为题的提示中限制了数组中数字的大小为 0 到 1000，因此我们用一个长度为 1001 的 int 数组即可统计数字出现的次数。
首先用数组保存 nums1 中数字出现的次数，同样的操作对 nums2 也来一遍，然后对比两个统计结果数组，然后直接从头开始对比两个统计数组的每一个位置，都不为 0，那就是重复数字，索引就是结果，然后这样全部遍历完，返回结果即可。
这个题目跟 242. 有效的字母异位词 中的做法基本一致，那道题用字符的 ASCII 码作为数组下标，然后用数组来保存字符出现的次数，这个题目数组里面是数字，不是可以直接用数字做数组下标吗？可以是可以，但是如果数组中的数字的大小没有限制，那么我们就无法申请一个固定大小的数组，Java 中，int 的最大值是 2147483647 我们总不能申请一个长度为 2147483647 的数组吧，这样算法占用的空间会超，是这个题的提示中限制了数组中数字的大小为 0 到 1000，所以我们用一个长度为 1001 的 int 数组保存即可。那如果数字大小没有限制呢，那我们就只有用 Map 来统计数字（或者字符）的出现次数了。比如 1. 两数之和
解题
public int[] intersection(int[] nums1, int[] nums2) {
int shortLength = nums1.length>nums2.length?nums2.length:nums1.length;
int[] result = new int[shortLength];
int resultIndex =0;
int[] number1Count = new int[1001];
for(int i=0;i<nums1.length;i++){
int index = nums1[i];
// 重复数字不重复计算
if(number1Count[index]==0){
number1Count[index]++;
}
}
int[] number2Count = new int[1001];
for(int i=0;i<nums2.length;i++){
int index = nums2[i];
// 重复数字不重复计算
if(number2Count[index]==0){
number2Count[index]++;
}
}
for(int i=0;i<1001;i++){
if(number1Count[i]>0 && number2Count[i]>0){
result[resultIndex]=i;
resultIndex++;
}
}
int[] finalResult = new int[resultIndex];
for(int i=0;i<resultIndex;i++){
finalResult[i]=result[i];
}
return finalResult;
}
精简之后
public int[] intersection(int[] nums1, int[] nums2) {
List<Integer> list = new ArrayList<>();
int[] numsCount1 = numCount(nums1);
int[] numsCount2 = numCount(nums2);
for (int i = 0; i < numsCount1.length; i++) {
if (numsCount1[i] > 0 && numsCount2[i] > 0) {
list.add(i);
}
}
// 因为不知道结果长度，所以只能用List
int[] result = new int[list.size()];
int index = 0;
for (Integer val : list) {
result[index++] = (int) val;
}
return result;
}
public int[] numCount(int[] nums) {
int[] numCOunt = new int[1001];
for (int i = 0; i < nums.length; i++) {
numCOunt[nums[i]]++;
}
return numCOunt;
}