29

O(n)時間の複雑さで解決する問題が与えられました：

「数と数 x のリストが与えられました。リストに合計 x になる 2 つの数があるかどうかを調べますか?」

そして、これが私の解決策です:

public class SumMatchResult {

  public static void main(String[] args){
    int[] numberList = {6,1,8,7,4,6};
    int requiredSum = 8;
    boolean isSumPresent = checkSumPresentHash(numberList,requiredSum);
    if(isSumPresent) {
      System.out.println("Numbers exist");
    }else {
      System.out.println("Numbers donot exist");
    }
  }

  private static boolean checkSumPresentHash(int[] numberList, int requiredSum) {
    Map<Integer, Integer> m = new HashMap<Integer,Integer>();
    int count = 0;
    for(int i=0;i<numberList.length;i++){
      m.put(i, numberList[i]);
    }
    for(int i=0;i<numberList.length;i++){
      if(m.containsValue(requiredSum - numberList[i])){
        count++;
      }
    }
    if(count>1){
        return true;
    }
    return false;
  }

}

入力に同じ値が含まれる可能性があるシナリオを考慮しなければならないため、確かに複雑な a を使用HashMap.containsValue()する代わりに使用しています。たとえば、上記の場合、 に一致する一連の入力値を持つことができ、これは を返す必要があります。HashSet.contains()O(1){3,6,4,4,7}sum 8true

HashMap.containsValue()上記のソリューションの時間の複雑さは、メソッドの複雑さに依存します。メソッドの時間の複雑さに光を当てて、時間の複雑さのcontainsValue()点で上記の問題に対するより良い解決策があるかどうかを提案してください。ありがとうございました。

4

4 に答える 4

23

タイトルの質問に答えるには - 他の人が述べたように、containsValueO(n) です。キーがないと、それがどこにあるかわからず、アルゴリズムはマップに格納されているすべての値を調べる必要があるためです。

質問の本文の質問に答えるには、それを解決する方法について、各数値について見たインスタンスの数をカウントできる一般的なマップが本当に必要かどうかを検討してください。つまり、数字が複数出現するかどうかを気にするのは、x/2 のときだけですよね? それは私にとってコーナーケースのようなにおいがします。if (numberList[i] == requiredSum/2) half++そのコーナーケースをチェックするテストを追加するだけです - set-construction ループ中とその後の埋め込みのようなものですif (requiredSum % 2 == 0 && half == 2) return true(以下の他のバリエーションを参照)。

次に、セットを反復処理し、各アイテムについてセットにrequiredSum-itemも含まれているかどうかを確認します。

要約すると (可能な場合は早期終了します):

Set<Integer> seen = new HashSet<Integer>();
boolean halfSeen = false;
for (int num : numberList) {
    if (num == requiredSum/2 && requiredSum % 2 == 0) {
        if (halfSeen) return true;
        halfSeen = true;
    } else {
        seen.add(num);
    }
}
for (int num : seen) {
    if (seen.contains(requiredSum - num)) return true;
}
return false;
于 2013-05-26T08:47:06.300 に答える