亞最大尺寸的給定約束

我整數數組的數組列表如下 -亞最大尺寸的給定約束

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

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

亞最大尺寸的給定約束

回答

相關問題