给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2] ## 示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4] ## 说明:
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
题意
实质就是对两个集合做交集运算,输出结果。
注意结果集中不能有重复元素。 # 思路 - 用第一个数组的元素与第二个数组的元素挨个比较，如果相同筛选出来。 如果用上面的思路的话无法辨别每个数组内的相同元素，就导致筛选出的结果集可能有相同元素。（不符合题意） # 调整思路？如何筛选出每个数组中相同的元素呢？ - 想想数据结构和算法书籍上相关的知识点？对数组的操作知识点：1.排序2.查找 如果我们对数组进行排序后，就可以比较相邻的两个元素，筛掉相同的元素，果然考点即知识点。 ----- ## 测试用例 写代码之间首先写好测试用例，考虑到边界条件及特殊情况，这样才能写出高质量的代码。
- nums1或nums2为空数组
- 其中一个数组有两个重复元素:[1,2,2],[1,2]
- 两个数组都有重复元素[1,2,2],[1,2,2]
- 其中一个数组有三个以上的重复元素[1,2,2,2],[1,2]
- 设计代码时需要考虑以上边界条件或是特殊样例。
public int[] intersection(int[] nums1, int[] nums2) { List list = new ArrayList(); Arrays.sort(nums1);//排序 Arrays.sort(nums2);//排序 for(int i=0;i<=nums1.length-1;i++){//排除相同的元素 while(i+1<=nums1.length-1&&nums1[i]==nums1[i+1]){//如果有相同的元素游标向前移动 i++; } for(int j=0;j<=nums2.length-1;j++){ while(j+1<=nums2.length-1&&nums2[j]==nums2[j+1]){//如果有相同的元素游标向前移动 j++; } if(nums1[i]==nums2[j]){//比较两个数组的元素是否相同 list.add(nums1[i]); } } } int[] result=new int[list.size()]; for(int i=0;i<=list.size()-1;i++) result[i]=(Integer)list.get(i); return result; }代码完成后，先别急着提交，可以自己按照测试用例做单元测试。
时间复杂度：
n^2 (n*m)
哇,这个代码效率也太低了呀,一般算法题的效率都可以优到常量或者对数级别。
优化思路：
其实这里两层for循环实质上是在nums2数组中进行查找操作。
咦！对连续的有序数列进行查找我们可以用二分查找，这样效率大大滴提升啊，嘻嘻嘻。
废话了这么多，改贴代码了。 ``` public static int[] intersection2(int[] nums1, int[] nums2) {
List list = new ArrayList();
Arrays.sort(nums1);//排序
Arrays.sort(nums2);//排序
for(int i=0;i<=nums1.length-1;i++){
while(i+1<=nums1.length-1&&nums1[i]==nums1[i+1]){//如果有相同的元素,游标向前移动
i++;
}
if (Arrays.binarySearch(nums2,nums1[i])>=0) {//二分查找两个数组中是否有相同的元素
list.add(nums1[i]);
}
}
int[] result=new int[list.size()];
for(int i=0;i<=list.size()-1;i++) result[i]=(Integer)list.get(i);
return result; } ``` ### 时间复杂度:nlog(m)
提交代码,平台测试用时较第一个少了一个数量级，nice。