两个数组的交集 II
描述:
给定两个数组, 编写一个函数来计算它们的交集.
示例:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
说明:
输出结果中每个元素出现的次数, 应与元素在两个数组中出现的次数一致.
我们可以不考虑输出结果的顺序.
思路:
我们可以用遍历穷举的方法, 但是时间复杂度肯定很高. 不妨换个思路: 先将数组递增排序, 排序之后将两个数组同时遍历 (定义两个数组的脚本变量, 初始值为 0, 向后遍历), 比较同索引位置的元素是否相等, 如果相等, 则记录下该值; 如果不相等, 将值较小的数组的脚标加 1, 另一个数组的脚标等待. 然后继续遍历比较, 直到遍历完短的数组.
代码如下:
- import java.util.Arrays;
- public class Intersect {
- public int[] intersect (int[] nums1, int[] nums2) {
- if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
- return new int[]{};
- }
- Arrays.sort(nums1);
- Arrays.sort(nums2);
- int i = 0, j = 0, k = 0;
- int[] result = new int[Math.min(nums1.length, nums2.length)];
- while (i <nums1.length && j < nums2.length) {
- if (nums1[i] == nums2[j]) {
- result[k++] = nums1[i];
- i++;
- j++;
- continue;
- } else if (nums1[i]> nums2[j]) {
- j++;
- } else {
- i++;
- }
- }
- return Arrays.copyOf(result, k); // 拷贝数组
- }
- public static void main(String[] args) {
- int[] nums1 = {1,2,2,1};
- int[] nums2 = {2,2};
- Intersect intersect = new Intersect();
- int[] result = intersect.intersect(nums1, nums2);
- //Arrays.toString() 方法将 hash 值转为数组
- System.out.println(Arrays.toString(result));
- }
- }
来源: http://www.jianshu.com/p/c106bd6823f1