题目要求
1
2
3
4
5
6
7
8
| Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
Each element in the result must be unique.
The result can be in any order.
|
找出两个无序数组中重合的值。
思路一：排序
思路一模仿了归并排序的merge部分。先将两个数组分别排序，排序完成之后再用两个指针分别比较两个数组的值。如果两个指针指向的值相同，则向结果集中添加该元素并且同时将两个指针向前推进。否则指向的值较小的那个指针向前推进。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
List<Integer> nums3 = new ArrayList<Integer>();
int i=0, j=0;
while(i<nums1.length && j<nums2.length){
if(nums1[i]==nums2[j])
{
if(!nums3.contains(nums1[i]))
nums3.add(nums1[i]);
i++;
j++;
}
else if(nums1[i]>nums2[j])
j++;
else
i++;
}
int[] arr = new int[nums3.size()];
for(int k=0;k<nums3.size();k++)
arr[k]=nums3.get(k);
return arr;
}
|
受排序算法影响，该方法的时间复杂度为O(nlgn）
思路二：建立索引
一方面排序对时间的消耗很大，另一方面数组中如果出现重复的值，也意味着大量无效的遍历。那么如何才能够在不便利的情况下获取二者的重合值。答案是为其中一个数组通过建立索引的方式排序。
什么叫建立索引的方式排序？这是指先获取数组中的最大值max和最小值min，然后将整数数组转化为一个长度为max-min+1的布尔型数组，布尔型数组i位置上的值代表原整数数组中是否存在数组i+min。如[1,6,7,0]对应的布尔型数组为[true,true,false,false,false,false,true,true]。这实际上是一种空间换时间的做法。通过这种方式，我们就可以在O(n)的时间复杂度内完成搜索。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public int[] intersection2(int[] nums1, int[] nums2){
if(nums1==null || nums2==null || nums1.length == 0 || nums2.length == 0){
return new int[0];
}
int max = nums1[0], min = nums1[0];
for(int n : nums1){
if(n > max) max = n;
else if(n < min) min = n;
}
boolean[] index = new boolean[max - min + 1];
for(int n : nums1){
index[n - min] = true;
}
int count = 0;
int[] tmp = new int[Math.min(nums1.length, nums2.length)];
for(int n : nums2){
if(n>=min && n<=max && index[n-min]){
tmp[count++] = n;
index[n-min] =false;
}
}
return count == tmp.length ? tmp : Arrays.copyOf(tmp, count);
}
|