如果我有一個二維陣列：
input[][] = { {"A", "B"}, {"C", "D"}, {"B", "A"}, {"C", "E"} }
我想要一個回傳的演算法
{("A", "B")} or {("B", "A")}
我知道有一個使用 HashMap 的解決方案，但我想解決這個問題。它不需要是最有效的解決方案。我想在 O(n log n) 時間內實作它，所以我不想使用 HashMap。我正在考慮對輸入陣列進行排序并比較元素，但我不知道如何實作它。任何人都可以提供一些幫助嗎？
uj5u.com熱心網友回復：
蠻力
有蠻力方法：對于每一對，看看它的反面是否也存在。所以當你有 (A, B) 時，看看你是否能找到 (B, A) （在你的例子中你可以）。下次你有(C, D)時，看看你能不能找到(D, C)（這次你不能）。使用嵌套回圈。在外回圈中遍歷對。在內部回圈中再次迭代這些對。如果內環中的一對與外環中的一對相反，則列印兩對。
該方法的時間復雜度為 O(n ^ 2)（可能很明顯）。
快樂編碼。
更有效：首先對對進行排序
在開始之前對對進行排序將允許您對反向對使用二分搜索。按第一個成員排序，然后按第二個成員排序。在您的示例中，排序順序將是
(A, B), (B, A), (C, D), (C, E)
再次迭代這些對。當你得到 (A, B) 時，使用二分搜索找到 (B, A)。當你得到 (C, D) 時，搜索 (D, C)。我應該按照排序的順序在 (C, E) 之后，因為那里什么都沒有，所以找不到這對。
如果您使用良好的排序演算法，后一種方法的時間復雜度應該為 O(n log n)。
uj5u.com熱心網友回復：
通過哈希集
static String[] findSymmetricPairByHashSet(String[][] input) {
record Entry(String a, String b) {}
Set<Entry> set = new HashSet<>();
for (String[] a : input) {
Entry p = new Entry(a[1], a[0]);
if (set.contains(p))
return new String[] {p.a, p.b};
set.add(new Entry(a[0], a[1]));
}
return null;
}
按樹集
static String[] findSymmetricPairByTreeSet(String[][] input) {
Set<String[]> set = new TreeSet<>(Arrays::compare);
for (String[] a : input) {
if (set.contains(a))
return a;
set.add(new String[] {a[1], a[0]});
}
return null;
}
按排序
static String[] findSymmetricPairBySort(String[][] input) {
Arrays.sort(input, Arrays::compare);
for (String[] a : input)
if (Arrays.binarySearch(input, new String[] {a[1], a[0]},
Arrays::compare) >= 0)
return a;
return null;
}
測驗：
public static void main(String[] args) throws IOException {
String[][] input = {{"A", "B"}, {"C", "D"}, {"B", "A"}, {"C", "E"}};
System.out.println(Arrays.toString(findSymmetricPairByHashSet(input)));
System.out.println(Arrays.toString(findSymmetricPairByTreeSet(input)));
System.out.println(Arrays.toString(findSymmetricPairBySort(input)));
}
輸出：
[A, B]
[B, A]
[A, B]
uj5u.com熱心網友回復：
這是一種似乎有效的方法。它不需要任何排序。
String[][] input = { {"A", "B"}, {"C", "D"}, {"B", "A"}, {"C", "E"} };
- 首先，將連接的陣列項復制到一個集合中。
- 然后遍歷陣列，進行反向連接并查看集合是否包含該字串。
- 如果是這樣，洗掉兩個連接的字串并列印陣列。
Set<String> set = new HashSet<>();
for (String[] arr : input) {
set.add(arr[0] arr[1]);
}
for(String[] arr : input) {
String item1 = arr[1] arr[0];
String item2 = arr[0] arr[1];
if (set.contains(item1)) {
set.remove(item1);
set.remove(item2);
System.out.println(Arrays.toString(arr));
}
}
印刷
[A, B]
上述替代方案是放棄串聯和使用Arrays.equals()，尤其是對于較大尺寸的陣列。在這種情況下，我認為Arrays.equals()是矯枉過正。代替列印，陣列可以保存在另一個資料結構中。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/373429.html