從行組合

Question

我想檢查它存在或不存在的數據值的組合。下面的代碼工作正常，但它看起來效率低下。我正在尋找這個問題的一些很好的解決方案。

public static void main(String args[]) { 

    Integer data[] = { 
      1, 2, 5, 1, 9, 3, 5, 3, 2 
    }; 

    Integer combination[] = { 
      1, 3 ,2 
    }; 

    System.out.println("Result: " + combinations(data, combination)); 
} 


public static boolean combinations(Integer dataset[], Integer combination[]) { 

    boolean results[] = new boolean[combination.length]; 

    Integer count = 0; 
    for (Integer comb : combination) { 

     for (Integer data : dataset) { 
      if (data.equals(comb)) { 
       results[count++] = true; 
       break; 
      } 
     } 

    } 

    for (Boolean result : results) { 
     if (!result) { 
      return false; 
     } 
    } 
    return true; 
} 

強文本

Answer 1

由於您的數據由它實現了「可比」的整數，我建議你利用這一點，構建一個TreeSet，所有的數據添加到它。然後你可以運行一個contains（）來查找一個元素是否存在於TreeSet中。 TreeSet保證每個添加，刪除和包含的日誌（n）成本。 添加所有元素（n）將耗費您n log（n）。 查找是否存在「m」個元素將花費您 log（n）。

Answer 2

排序數據集組是複雜n日誌（N）。 （快速或合併排序可能？）然後運行二進制搜索組合數組的每個成員在數據集上。二進制搜索複雜度log（n）。當你爲組合數組的每個成員執行此操作時，複雜度將爲nlog（n）。

nlog（n）+ nlog（n）= 2nlog（n）它是O（nlogn）。這樣你的表現會增加。

---

代碼

public static boolean combinations(Integer dataset[], Integer combination[]) { 

sort(dataset); // quick or insertion sort, nlogn 


for (Integer comb : combination) { // n 

    if (!binarysearch(dataset, comb)) //logn 
     return false; 
} //n*logn = nlogn 

return true;} //2nlogn = O(nlogn) 

Answer 3

您可以從數組更改爲ArrayList並使用containsAll方法。不確定它是否足夠有效，但會縮短您的代碼。

public static void main(String args[]) { 
    Integer data[] = {1, 2, 5, 1, 9, 3, 5, 3, 2}; 
    Integer combination[] = {1,3 ,2}; 
    System.out.println("Result: " + combinations(data, combination)); 
} 
public static boolean combinations(Integer dataset[], Integer combination[]) { 
    List<Integer> data = Arrays.asList(dataset); 
    List<Integer> comb = Arrays.asList(combination); 
    return data.containsAll(comb); 
} 

Answer 4

看起來你只是想檢查組合是否是你的數據集的一個子集......它出現在你的數據集中的順序並不重要。那是對的嗎？

您的數據集有多大？數據集是在需要時創建的，還是始終保留下來的？

如果數據集很大並且始終保持不變，那麼搜索是否可以更容易地進行排序。

for (Integer comb : combination) { 
    if (Arrays.binarySearch(dataset, comb) < 0) 
     return false; //If any element is not found, return false 
    } 
} 
return true; 

如果您還可以保持組合的排序，您可以進一步優化它。

int loc = 0; 
for (Integer comb : combination) { 
    loc = Arrays.binarySearch(dataset, loc, data.length, comb); 
    //Since both are sorted, u can be sure that next element will be 
    //after previous element match 
    if (loc < 0) 
     return false; 
    } 
} 
return true; 

即使你不能保持一個有序數組，一個優化ü可以做的是擺脫布爾數組和底部的for循環的。算法如下...

boolean isMatch = false; 
for (Integer comb : combination) { 
    //We will be here in two condition - 
    // 1. first iteration or previous element was found in dataset. 
    // 2. Just set to false to check next element. Reset the flag 
    boolean isMatch = false; 
    for (Integer data : dataset) { 
     if (data.equals(comb)) { 
      //match found for the current combination element 
      isMatch = true; 
      break; 
     } 
    } 
    //This mean one of the combination element is not there. Break out. 
    if (!isMatch) break; 
} 
return isMatch;