News:三分天注定,七分靠打拼,爱拼才会赢!致力打造专业IT博客。如果你对本博客有任何意见或建议请联系作者,邮箱:blog@caokuan.cn

求两个数组的交集

逝水无痕 481 0 条

在我们做业务开发的过程中可能会遇到求两个数组的交集或者相似情况的问题,那么在解决这个问题的时候就需要我们思考一下了,因为解题的方法很多,效率上的差异可能会很大。有的同学也许不太在意效率上的问题,认为解决问题就行了,其实不然,在一些效率要求非常高的场景中,低效的解题方法可能会拖垮系统,因此找到一种高效的方法就显得很重要了。在我们日常开发的过程中思考算法是我们提高代码能力的重要途径,坚持不懈,能力一定会提高。下面的各个想法是我在思考解题的过程中产生的,将他们总结下来,希望能起到抛砖引玉的作用。

数组交集.jpg

给定两个数组

int[] arr = {1, 5, 3, 6, 4, 4, 16, 20, 3, 2, 6, 10, 12, 16, 30, 1, 5, 3, 6, 4, 4, 16, 20, 3, 2, 6, 10, 12, 16, 30, 82, 93, 51, 41, 27, 74, 84, 93};

int[] arr2 = {10, 3, 4, 40, 10, 20, 4, 6, 4, 3, 6, 5, 2, 10, 33, 10, 3, 4, 40, 10, 20, 4, 6, 4, 3, 6, 5, 2, 10, 33, 45, 88, 66, 65, 49, 98, 37, 19};

1.暴力对比

这种方法是思路上最简单的,直接循环比较两个数组中是否有相同的元素,找到这些元素后去重即可得到结果。

Set<Integer> result = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr2.length; j++) {
        if (arr[i] == arr2[j]) {
            result.add(arr2[j]);
            break;
        }
    }
}

2.使用哈希

使用 HashSet 解题

Set<Integer> set = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
    set.add(arr[i]);
}
Set<Integer> set2 = new HashSet<>();
for (int i = 0; i < arr2.length; i++) {
    set2.add(arr2[i]);
}
List<Integer> result = new ArrayList<>();
for (Integer it : set) {
    if (!set2.add(it)) { // 利用 add 返回值:true 表示原 set 里没有这个新添加的元素;false 表示原来有这个新添加的元素
        result.add(it);
    }
}

使用 HashMap 解题

Map<Integer, Integer> map = new HashMap<>(arr.length);
for (int i = 0; i < arr.length; i++) {
    map.put(arr[i], -1);
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < arr2.length; i++) {
    Integer value = map.put(arr2[i], 0); // put 的返回值为 key 对应的 old value
    if (value != null && value == -1) { // 当 old value 为 -1 则说明是交集元素
        result.add((arr2[i]));
    }
}

3.使用大数组

思路是建立两个大数组,将需要求交集的两个数组的元素挨个当作角标放到新数组中,这样最后只要对比两个数组相同角标的数据就可以知道是不是交集元素了。

int[] tmp1 = new int[100];
for (int i = 0; i < arr.length; i++) {
    tmp1[arr[i]] = 1;
}
int[] tmp2 = new int[100];
for (int i = 0; i < arr2.length; i++) {
    tmp2[arr2[i]] = 1;
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < 100; i++) {
    if (tmp1[i] == 1 && tmp2[i] == 1) {
        result.add(i);
    }
}

其他

以上的3种思路的时间复杂度是逐渐降低的。当然这里还有许多其他的解题思路,就不再一一列举了,希望读者不要停下思考的脚步。书山有路勤为径,学海无涯苦作舟。

发表我的评论
icon_mrgreen.gificon_neutral.gificon_twisted.gificon_arrow.gificon_eek.gificon_smile.gificon_confused.gificon_cool.gificon_evil.gificon_biggrin.gificon_idea.gificon_redface.gificon_razz.gificon_rolleyes.gificon_wink.gificon_cry.gificon_surprised.gificon_lol.gificon_mad.gificon_sad.gificon_exclaim.gificon_question.gif

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址