至少包含两个元素的最小交集-算法

发布时间:2024年01月22日

题目

给定一个集合source={{1,4},{3,6},{8,10}},其中{1,4}表示包含1,2,3,4元素的数组,求一个数组与source中的所有数组都有交集,并且包含至少两个元素,如result = {3,4,8,9},总共四个元素。其中3,4分别与{1,4}{3,6}有3,4交集,因此只需要两个元素即可。而{8,10}与另外两个都没有交集,因此结果集合需要额外8,9元素

解题

使用贪心算法,贪的是两种情况,

一种是在不知道当前集合的子交集时,选择最左边的两个元素与前面去求交集。

比如{1,2},{4,8},一开始应该选择4,5两个元素去个{1,2}求交集,最可能有交集。

第二种是在已经确定当前集合的子交集时,需要尽量包含前面集合,能包含时,后者就不用再提供一个交集元素了

比如{1,5},{2,5},{5,8},确定了中间集合中起码有一个数字5是交集内,另一个元素应该是最左边界2

第三种也是在已经确定当前集合的子交集时,也需要尽量包含前面集合,但可能包不上,这是就需要让后者自己提供一个了

比如{2,4},{2,5},{5,8},确定了中间集合中起码有一个数字是5是交集内,另一个元素应该是最左边界2,但是4达不到5边界,需要他自己提供一个,比如3或者4

private static int findMinSetContain2LeastItem(int[][] source) {
  Arrays.sort(source, (a, b) -> {
    if (a[0] == b[0]) {
      return b[1] - a[1];
    }
    return a[0] - b[0];
  });
  int res = 2;
  int cur = source[source.length - 1][0];
  int biggerThanCur = source[source.length - 1][0] + 1;
  for (int i = source.length - 2; i >= 0; i--) {
    int preB = source[i][1];

    if (preB >= biggerThanCur) {
      continue;
    } else if (preB < cur) {
      cur = source[i][0];
      biggerThanCur = source[i][0] + 1;
      res += 2;
    } else {
      res++;
      biggerThanCur = cur;
      cur = source[i][0];
    }
  }
  return res;
}

文章来源:https://blog.csdn.net/u010187815/article/details/135724605
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。