algorithm - 2-SUMの線形時間アルゴリズム

Question

整数xとN個の異なる整数のソートされた配列aが与えられた場合、線形時間アルゴリズムを設計して、a [i] + a [j]==xとなる2つの異なるインデックスiとjが存在するかどうかを判断します。

score 40 · Accepted Answer

これが私の解決策です。それが以前に知られていたかどうかはわかりません。2つの変数iとjの関数の3Dプロットを想像してみてください。

sum(i,j) = a[i]+a[j]

に最も近いものがiあります。これらのペアはすべて、 xに最も近い線を形成します。この線に沿って歩き、以下を探す必要があります：ja[i]+a[j]x(i,j)a[i]+a[j] == x

 int i = 0; 
 int j = lower_bound(a.begin(), a.end(), x)  -  a.begin(); 
 while (j >= 0 && j < a.size()  &&  i < a.size())  {  
    int sum = a[i]+a[j]; 
    if (sum == x)   { 
        cout << "found: " << i << " " << j << endl;  
        return;
    }
    if (sum > x)    j--;
    else            i++;
    if (i > j) break;
 }  
 cout << " not found\n";

複雑さ：O（n）

score 13 · Accepted Answer

補数の観点から考えてください。

リストを繰り返し、各アイテムについて、その番号のXに到達するために必要な番号を把握します。棒指数と補数をハッシュに入れます。繰り返しながら、数値またはその補数がハッシュに含まれているかどうかを確認します。もしそうなら、見つかりました。

編集：そして私には時間がありますが、いくつかの疑似的なコードです。

boolean find(int[] array, int x) {
    HashSet<Integer> s = new HashSet<Integer>();

    for(int i = 0; i < array.length; i++) {
        if (s.contains(array[i]) || s.contains(x-array[i])) {
            return true;
        }
        s.add(array[i]);
        s.add(x-array[i]);
    }
    return false;
}

score 2 · Accepted Answer

> ceil（x / 2）である最初の値の初回通過検索。この値をLと呼びましょう。
Lのインデックスから、合計に一致する他のオペランドが見つかるまで逆方向に検索します。

2 * n〜O（n）です

これは二分探索に拡張できます。

Lがmin（> ceil（x / 2）の要素）であるようなLが見つかるように、二分探索を使用して要素を検索します。
Rについても同じことを行いますが、配列内の検索可能な要素の最大サイズとしてLを使用します。

このアプローチは2*log（n）です。

score 2 · Accepted Answer

これは、辞書のデータ構造と数値の補数を使用したPythonバージョンです。これには線形実行時間があります（Nの順序：O（N））：

def twoSum(N, x):
    dict = {}

    for i in range(len(N)):
        complement = x - N[i]
        if complement in dict:
            return True
        dict[N[i]] = i

    return False

# Test
print twoSum([2, 7, 11, 15], 9) # True
print twoSum([2, 7, 11, 15], 3) # False

score 2 · Accepted Answer

配列がソートされている場合（降順でWLOG）、次のことができます。アルゴリズムA_1：（a_1、...、a_n、m）、a_1 <...、<a_nが与えられます。リストの一番上と一番下にポインタを置きます。両方のポインターがある合計を計算します。合計がmより大きい場合は、上のポインタを下に移動します。合計がm未満の場合は、下のポインターを上に移動します。ポインタがもう一方にある場合（ここでは、各番号は1回しか使用できないと想定しています）、unsatを報告します。それ以外の場合（同等の合計が見つかります）、レポートは座っています。

計算される合計の最大数は正確にnであるため、これがO（n）であることは明らかです。正しさの証明は演習として残されています。

これは、SUBSET-SUMのHorowitz and Sahni（1974）アルゴリズムのサブルーチンにすぎません。（ただし、ほとんどすべての汎用SSアルゴリズムには、Schroeppel、Shamir（1981）、Howgrave-Graham_Joux（2010）、Becker-Joux（2011）などのルーチンが含まれていることに注意してください。）

順序付けされていないリストが与えられた場合、Mergesortを使用してリストをソートし、A_1を適用できるため、このアルゴリズムの実装はO（nlogn）になります。

score 1 · Accepted Answer

配列を繰り返し処理し、修飾された数値とそのインデックスをマップに保存します。このアルゴリズムの時間計算量はO（n）です。

vector<int> twoSum(vector<int> &numbers, int target) {
    map<int, int> summap;
    vector<int> result;
    for (int i = 0; i < numbers.size(); i++) {
        summap[numbers[i]] = i;
    }
    for (int i = 0; i < numbers.size(); i++) {
        int searched = target - numbers[i];
        if (summap.find(searched) != summap.end()) {
            result.push_back(i + 1);
            result.push_back(summap[searched] + 1);
            break;
        }
    }
    return result;
}

score 0 · Accepted Answer

私はこのようなものに違いを追加しますHashSet<T>：

public static bool Find(int[] array, int toReach)
{
    HashSet<int> hashSet = new HashSet<int>();

    foreach (int current in array)
    {
        if (hashSet.Contains(current))
        {
            return true;
        }
        hashSet.Add(toReach - current);
    }
    return false;
}

score 0 · Accepted Answer

注：コードは私のものですが、テストファイルはそうではありませんでした。また、ハッシュ関数のこのアイデアは、ネット上のさまざまな読み取り値から来ています。

Scalaでの実装。値にhashMapとカスタム（まだ単純な）マッピングを使用します。初期配列のソートされた性質を利用しないことに同意します。

ハッシュ関数

各値を10000で割ってバケットサイズを固定します。その数は、バケットに必要なサイズによって異なる可能性があり、入力範囲に応じて最適化できます。

したがって、たとえば、キー1は1から9までのすべての整数を担当します。

検索範囲への影響

つまり、現在の値nに対して、 n + c = x（xは2-SUMを見つけようとしている要素）などの補集合cを探している場合、次のようになります。補集合が可能なバケットは3つだけです。

-鍵
-キー+1
-キー-1

あなたの番号が次の形式のファイルにあるとしましょう：

これがScalaでの実装です

import scala.collection.mutable                                                                                                                                                                       
import scala.io.Source

object TwoSumRed {
  val usage = """ 
    Usage: scala TwoSumRed.scala [filename]
  """

  def main(args: Array[String]) {
    val carte = createMap(args) match {
      case None => return
      case Some(m) => m
    }

    var t: Int = 1

    carte.foreach {
      case (bucket, values) => {
        var toCheck: Array[Long] = Array[Long]() 

        if (carte.contains(-bucket)) {
          toCheck = toCheck ++: carte(-bucket)
        }
        if (carte.contains(-bucket - 1)) {
          toCheck = toCheck ++: carte(-bucket - 1)
        }
        if (carte.contains(-bucket + 1)) {
          toCheck = toCheck ++: carte(-bucket + 1)
        }

        values.foreach { v =>
          toCheck.foreach { c =>
            if ((c + v) == t) {
              println(s"$c and $v forms a 2-sum for $t")
              return
            }
          }
        }
      }
    }
  }

  def createMap(args: Array[String]): Option[mutable.HashMap[Int, Array[Long]]] = {
    var carte: mutable.HashMap[Int,Array[Long]] = mutable.HashMap[Int,Array[Long]]()

    if (args.length == 1) {
      val filename = args.toList(0)
      val lines: List[Long] = Source.fromFile(filename).getLines().map(_.toLong).toList
      lines.foreach { l =>
        val idx: Int = math.floor(l / 10000).toInt
        if (carte.contains(idx)) {
          carte(idx) = carte(idx) :+ l
        } else {
          carte += (idx -> Array[Long](l))
        }
      }
      Some(carte)
    } else {
      println(usage)
      None
    }
  }
}

score 0 · Accepted Answer

int[] b = new int[N];
for (int i = 0; i < N; i++)
{
    b[i] = x - a[N -1 - i];
}
for (int i = 0, j = 0; i < N && j < N;)
    if(a[i] == b[j])
    {
       cout << "found";
       return;
     } else if(a[i] < b[j])
        i++;
     else
        j++;
cout << "not found";

score 0 · Accepted Answer

これが線形時間計算量の解ですO（n）時間O（1）空間

 public void twoSum(int[] arr){

   if(arr.length < 2) return;

   int max = arr[0] + arr[1];
   int bigger = Math.max(arr[0], arr[1]);
   int smaller = Math.min(arr[0], arr[1]);
   int biggerIndex = 0;
   int smallerIndex = 0;

    for(int i = 2 ; i < arr.length ; i++){

        if(arr[i] + bigger <= max){ continue;}
        else{
            if(arr[i] > bigger){
                smaller = bigger;
                bigger = arr[i];
                biggerIndex = i;
            }else if(arr[i] > smaller)
            {
                smaller = arr[i];
                smallerIndex = i;
            }
            max = bigger + smaller;
        }

    }

    System.out.println("Biggest sum is: " + max + "with indices ["+biggerIndex+","+smallerIndex+"]");

}

score 0 · Accepted Answer

解決

インデックスを格納するための配列が必要です
配列が空であるか、2つ未満の要素が含まれているかどうかを確認してください
配列の開始点と終了点を定義します
条件が満たされるまで繰り返します
合計が目標と等しいかどうかを確認します。はいの場合、インデックスを取得します。
条件が満たされない場合は、合計値に基づいて左または右にトラバースします
右にトラバース
左にトラバースします

詳細情報：[ http://www.prathapkudupublog.com/2017/05/two-sum-ii-input-array-is-sorted.html

score 0 · Accepted Answer

leonidへのクレジット

あなたがそれにショットを与えたいなら、Javaでの彼の解決策

戻り値を削除したので、配列が並べ替えられているが、重複が許可されている場合でも、ペアが返されます

static boolean cpp(int[] a, int x) {
    int i = 0;
    int j = a.length - 1;
    while (j >= 0 && j < a.length && i < a.length) {
        int sum = a[i] + a[j];
        if (sum == x) {
        System.out.printf("found %s, %s \n", i, j);
//                return true;
        }
        if (sum > x) j--;
        else i++;
        if (i > j) break;
    }
    System.out.println("not found");
    return false;
    }

algorithm - 2-SUMの線形時間アルゴリズム

12 に答える 12

Related

Reference