logi sisse meist KKK

kellel igav..

meil on antud massiiv kus on suvalised täisarvud, nii samuti on meil antud sisendväärtus 'number1', massiivi elemendid on järjestatud.

'nuputamise' idee on leida algorithm mis leiaks kas massiivis on 2 sellist arvu mis summeeruks 'number1'ks..

et asi huvitavam oleks siis proovige algorithm teha nii, et selle kiirus jääks O(n), kus n on massiivi elemenetide arv..

küsitud Mar 21 '10 at 19:47

erti%202's gravatar image

erti 2
71347

edited Mar 21 '10 at 21:48


Kui vaja on ainult jah/ei vastust ja järjestus on kasvav (korduvate väärtuste korral mittekahanev), siis pakuks midagi sellist:

// kontrollib, kas massiivis a pikkusega n elementi
// on kaks erinevat elementi, mille summa on s
bool on_summa(const int a[], int n, int s) {
    int v = 0, p = n - 1;
    while (v < p) {
        int t = a[v] + a[p];
        if (t == s) return true;
        if (t < s) ++v;
        if (t > s) --p;
    }
    return false;
}

Tööpõhimõte on lihtne: alustame kahest äärmisest elemendist; kui nende summa on väiksem kui vaja, siis selle minimaalseks kasvatamiseks asendame vasakpoolse liidetava tema parema naabriga; kui nende summa on suurem kui vaja, siis selle minimaalseks kahandamiseks asendame parempoolse liidetava tema vasaku naabriga; kui kaks järjehoidjat kohtuvad või üksteisest mööduvad, oleme kõik võimalikud paarid läbi vaadanud ja sobivat summat ei olegi.

link

vastatud Mar 21 '10 at 22:52

Ahto%20Truu's gravatar image

Ahto Truu ♦♦
6596711

Mulle Rene lahenduse idee meeldis, aga kuna nägin võimalust sealt üks tsükkel välja optimiseerida, siis siin on minu variant:

// Detects if two elements in the array produce the given sum.
// Returns those two elements if they exist, false otherwise.
function findSum(arr, sum) {
  var seen = {};

  // go through the array and for each array element x
  // calculate the needed y so that x+y=sum, and check if
  // y has been seen. if not, record x as seen and continue.
  for (var i=0; i<arr.length; i++) {
    var x = arr[i];
    var y = sum - x;

    if (seen[y] !== undefined) {
      return [x, y];
    }

    seen[x] = true;
  }

  return false;
}

Muidugi Ahto variandiga see ei konkureeri, kuna vajab mälu O(n). Ja üleüldse on see üks petukas, kuna õiged mehed nii tühiste asjade jaoks hashtabeleid ei kasuta :). Aga mõte oli hea.

link

vastatud Mar 22 '10 at 21:49

Tambet%20Matiisen's gravatar image

Tambet Matiisen ♦♦
77791125

1

Heh, ma märkasin alles nüüd, et ülesande püstituses oli öeldud, et massiiv on järjestatud.

(Mar 22 '10 at 22:42) Rene Saarsoo ♦♦

Kasutades paisktabeli abi (JavaScriptis):

// Detects if two elements in the array produce the given sum.
// Returns those two elements if they exist, false otherwise.
function findSum(arr, sum) {
  // put all array elements to hash table
  var hash = {};
  for (var i=0; i<arr.length; i++) {
    hash[arr[i]] = i;
  }

  // go through the array again and for each array element x
  // calculate the needed y so that x+y=sum, and check if
  // hash table contains y.
  for (var i=0; i<arr.length; i++) {
    var x = arr[i];
    var y = sum - x;

    if (hash[y] !== undefined && hash[i] !== i) {
      return [x, y];
    }
  }

  return false;
}

Eeldusel, et paisktabelist järgi vaatamine toimub konstantse ajaga, peaks olema O(n).

link

vastatud Mar 22 '10 at 19:06

Rene%20Saarsoo's gravatar image

Rene Saarsoo ♦♦
1.1k101121

edited Mar 22 '10 at 19:18

Sinu vastus
lülita eelvaade

Jälgi seda küsimust

By Email:

Pärast sisselogimist saad tellida muudatuse teavitusi siit

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *kaldkiri* või __kaldkiri__
  • **paks kiri** või __paks kiri__
  • link:[tekst](http://url.com/ "pealkiri")
  • pilt?![alt tekst](/path/img.jpg "pealkiri")
  • nummerdatud nimekiri: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • põhilised HTML märgendid on samuti toetatud

Pinu tööpakkumised

kõik pakkumised »

Küsimuse sildid:

×7

küsitud: Mar 21 '10 at 19:47

nähtud: 2,913 korda

viimati uuendatud: Mar 24 '10 at 20:46

Litsents: Creative Commons Attribution License | Kontakt: info@pinu.ee