亚最大尺寸的给定约束

我整数数组的数组列表如下 -亚最大尺寸的给定约束

我想找到的最大尺寸的所有子集，使得

a1[0]<a2[0] && a1[1]<a2[1] && a1[2] <a2[2]

我did- 1）我按照升序对arraylist的每一行进行排序。 2）然后我排序利用比较整个数组列表所以我得到这个 -

但现在，我坚持。我不确定如何根据上述约束找到所有最大尺寸的子集。例如在上述情况下， -

是最大尺寸子集可能的。

来源

2016-07-31 Noober

你试过蛮力吗？只检查每个有效的组合？ – Andreas

不，我不确定如何获得所有组合，蛮力在时间复杂度上会呈指数级增长，但我认为它可以用于小数目，但我不知道如何继续 – Noober

您可以继续编写一种获取两个数组并返回一个布尔值。它会检查第一个数组是否在每个索引处的值都小于第二个数值。 – garnulf

考虑这个算法：

对于每个row，开始跟踪subset
对于随后的每个row2
1. 如果row < row2，然后加入到子集，并从步骤2递归地继续
比较subset大小与任何先前保存的子集：
1. 如果较大，则删除所有以前保存的子集，并保存这一个
2. 如果相等，则该子集添加到先前保存的子集的列表

虽然这种算法的时间复杂度是指数，这也很容易实现，并且可以受用较小的数据集。

List<List<int[]>> findMaximumSubsets(int[][] arr) { 
    List<List<int[]>> acc = new ArrayList<>(); 
    for (int i = 0; i < arr.length - 1; i++) { 
     findMaximumSubsets(arr, i, acc, new ArrayList<>(Collections.singletonList(arr[i]))); 
    } 
    return acc; 
} 

void findMaximumSubsets(int[][] arr, int row, List<List<int[]>> acc, List<int[]> current) { 
    for (int i = row + 1; i < arr.length; i++) { 
     if (comparator.compare(arr[row], arr[i]) < 0) { 
      // ... (not spoiling for you ...) 
     } 
    } 
} 

Comparator<int[]> comparator = new Comparator<int[]>() { 
    @Override 
    public int compare(int[] a1, int[] a2) { 
     int cmp1 = Integer.compare(a1[0], a2[0]); 
     if (cmp1 > -1) { 
      return 0; 
     } 
     int cmp2 = Integer.compare(a1[1], a2[1]); 
     if (cmp2 > -1) { 
      return 0; 
     } 
     return Integer.compare(a1[2], a2[2]); 
    } 
};

来源

2016-07-31 07:34:05 janos

是否真的允许在检查约束之前对各个数组进行排序？以下算法应该以任何方式工作。

以下算法应为O工作（N ）找到一个最大的集（你需要的一切。在这种情况下，最坏的情况下努力是指数）：

建立一个向无环图其中各个阵列是节点，并且当且仅当b可以根据约束遵循a时，节点a和b之间存在边。
对此图进行拓扑排序。
按排序顺序（从“最小”节点开始）遍历节点，并为每个节点x计算具有x作为“最大”节点的最大子集。这可以通过查看所有以前的节点来完成y：用包含x的子集进行初始化，然后对于所有y：如果x可以跟随y将x添加到为y计算的最大子集，如果该子集大于先前x的子集记得它最大。
在线性通过所有节点时找到总体最大的子集。

实施例：

已经在拓扑顺序。因此，我们通过线计算行：

14 27 62 -> 14 27 62 
15 85 92 -> 14 27 62, 15 85 92 
16 40 90 -> 14 27 62, 16 40 90 
23 61 78 -> 14 27 62, 23 61 78 
23 70 90 -> 14 27 62, 23 70 90 
25 93 98 -> 14 27 62, 15 85 92, 25 93 98

来源

2016-07-31 05:54:59 Henry

亚最大尺寸的给定约束

回答

相关问题