Rūšiuoti masyvą su minimaliais judesiais

Aš susidūriau su šia problema:

Yra n + 1 įkrovos dokai. >Pateikite algoritmą rūšiuoti dėžutes su minimaliu judėjimų skaičiumi .

Mano algoritmas (pseudokodas) (indeksas pagrįstas 1)

  • (0) Nustatyti skaitiklį 0
  • (1) Iteracija per masyvą, kad rastų lauką maks. Perkelkite jį į paskutinę lizdą (n + 1). didinimo skaitiklis pagal 1.

  • (2) Tada iš naujo paleiskite nuo pradžios iki riba = n_th lizdo, raskite maksimalų lauką ir pakeiskite jį iki galo. papildomas skaitiklis 3 (nes mainai turi 3 judesius).

  • (3) Sumažina limitą 1
  • Grįžkite į (2), kol pasieksite 1

Atnaujinta . Saruva Sahu pasiūlė labai malonų sprendimą, kurį optimizavau, kad būtų išvengta „pasidalijimo“.

  public static void moveToPos(int[] nums) { int tempLoc = nums.length - 1; final int n = nums.length - 2; // boxes --> loc Map<Integer, Integer> tracking = new HashMap<>(); for (int i = 0; i < n; ++i) { // if the target place is empty if (nums[i] == tempLoc) { // then move it there nums[tempLoc] = nums[i]; // new temp loc tempLoc = i; } else if(nums[i] != i) { // move current box at target out of the way nums[tempLoc] = nums[nums[i]]; if (tempLoc != nums[nums[i]]){ // nums[i] is not at the right place yet // so keep track of it for later tracking.put(nums[nums[i]], tempLoc); } nums[nums[i]] = nums[i]; tempLoc = i; } } // move the unstelled to its right place while (!tracking.isEmpty()) { // where is the box that is supposed to be at tempLoc int loc = tracking.remove(tempLoc); nums[tempLoc] = nums[loc]; // make the emtpy spot the new temp loc tempLoc = loc; } } 

Kas tai yra geriausias algoritmas?

3
28 авг. Vienas du trys yra 28 d. 2016-08-28 05:40 '16 at 5:40 am 2016-08-28 05:40
@ 4 atsakymai

Yra labai geras būdas išspręsti šią problemą. Tarkime, kad turime tokias eilutes.

 [5] 4 2 3 1 

Pakeiskite 1 >

 [1] 4 2 3 5 

Dabar pirmasis >

 1 [4] 2 3 5 

Pakeiskite antrąjį >

 1 [3] 2 4 5 

Dabar dar kartą patikrinkite, ar antrasis >

 1 [2] 3 4 5 

Dabar dar kartą patikrinkite, ar antrasis >

 1 2 [3] 4 5 1 2 3 [4] 5 1 2 3 4 [5] 

Kas tai yra. Dėžės bus rūšiuojamos.

Svarbu pažymėti:

  • Šis algoritmas veikia tik tais atvejais, kai visi masyvo numeriai yra nuoseklūs (rūšiavimas ar nerūšis). Šį reikalavimą patvirtina atsakovas komentarų skiltyje.
  • Kiekvieno apsikeitimo metu įdėkite bent 1 dėžutę į teisingą galutinę padėtį, tai yra geriausias šiame algoritme. Geriausiais atvejais į kiekvieną apsikeitimo sandorį galite įdėti 2 >
  • Kiekvienam apsikeitimui reikalingas tuščias laukas / erdvė, kurią galima įsigyti pagal poreikį.
  • Kiekvieną keitimą (tarp A ir B) sudaro 3 žingsniai. Perkeliant A į tuščią erdvę, tada perkelkite B į A padėtį ir tada perkelkite A atgal į senąją B. padėtį. Todėl A yra garantuota, kad gautų teisingą galinę padėtį.

Atnaujinimas : „Niko“ pasiūlytas algoritmas suteikia minimalų judėjimų skaičių, kaip parodyta toliau:

 5 4 2 3 1 [ ] : Start positions .. 4 2 3 1 [5] : 1st move 1 4 2 3 .. [5] : 2nd move 1 4 2 3 5 [ ] : 3rd move 1 .. 2 3 5 [4] : 4th move 1 2 .. 3 5 [4] : 5th move 1 2 3 .. 5 [4] : 6th move 1 2 3 4 5 [ ] : 7th move 

Tik 7 judesiai dėl didesnio laiko O (n ^ 2) sudėtingumo.

Kita vertus, mano siūlomas algoritmas garantuoja mažiausią O (n) sudėtingumo laiką, bet ne mažiausią judesių skaičių, kaip parodyta toliau:

 [5] 4 2 3 1 -> [1] 4 2 3 5 : 3 moves to swap 5 and 1 1 [4] 2 3 5 -> 1 [3] 2 4 5 : 3 moves to swap 4 and 3 1 [3] 2 4 5 -> 1 [2] 3 4 5 : 3 moves to swap 3 and 2 

Tik 9 žingsniai, turintys mažesnį laiką (O).

2
28 авг. Saurav Sahu atsakymas, pateiktas rugpjūčio 28 d 2016-08-28 06:16 '16 at 6:16 am 2016-08-28 06:16

Raskite bet kurį netinkamą lauką. Perkelkite jį į paskutinę stotelę. Tada raskite lauką, kuris turėtų būti pradinio pirmojo >

3
28 авг. atsakymas, kurį pateikė Nico Schertler 28 rug . 2016-08-28 05:54 '16 at 5:54 2016-08-28 05:54

C kodo be apsikeitimo sandorių pavyzdys naudojant [0] kaip tuščią lizdą ir daroma prielaida, kad nuo [1] iki [n] atsitiktine tvarka yra nuo 1 iki n. Kiekvienas [n] [n] judėjimas perkelia elementą į šią galutinę vietą. Algoritmas atitinka „ciklus“ permutacijoje.

 int i,j,k; // scan a[] from 1 to n for(i = 1; i <= n; i++){ if(i != a[i]){ // if element out of place, move to a[0] a[0] = a[i]; // follow the cycle to put elements in place j = i; do{ // find element that belongs in a[j] for(k = i; j != a[k]; k++); // move that element to a[j] a[j] = a[k]; j = k; }while(j != a[0]); // move a[0] to a[j] to complete rotate of cycle a[j] = a[0]; } } 

Kaip bendresnis pavyzdys, indeksų I [] masyvas yra surūšiuotas pagal reikšmių A [] masyvą, tada A [] ir I [] perkeliami pagal I [] eilutes, kiekvienas įrašas [], įdėjus elementą į jį []. rūšiuojama pozicija. Tai yra C ++ pavyzdys (naudoja lambda palyginimą).

 int A[8] = {7,5,0,6,4,2,3,1}; size_t I[8]; size_t i, j, k; int ta; // create array of indices to A[] for(i = 0; i < sizeof(A)/sizeof(A[0]); i++) I[i] = i; // sort array of indices according to A[] std::sort(I, I+sizeof(A)/sizeof(A[0]), [ i, size_t j){return A[i] < A[j];}); // reorder A[] and I[] according to I[] for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){ if(i != I[i]){ ta = A[i]; k = i; while(i != (j = I[k])){ A[k] = A[j]; I[k] = k; k = j; } A[k] = ta; I[k] = k; } } 
1
28 авг. atsakymą pateikė rcgldr 28 rug . 2016-08-28 12:48 '16 at 12:48 2016-08-28 12:48

TJO, efektyviausias yra algoritmas (jei „perkelti“ reiškia „apsikeisti“ ir leisti judėti į bet kurią vietą):

Tarkime, kad masyvo ilgis yra n . Apskaičiuojame ilgiausią didėjančią masyvo seką, tarkime, kad ilgiausio didėjančio sekos ilgis yra s , tada minimalūs judesiai yra n - s .

tai yra.

[2, 3, 5, 4, 1] , n yra 5, s yra 3 ( [2, 3, 5] ), todėl atsakymas yra 5 - 3 = 2

[5, 4, 2, 3, 1] , n yra 5, s yra 2 ( [2, 3] ), todėl atsakymas yra 5 - 2 = 3

0
28 авг. atsakymas, pateiktas pagal koderzą 28 rug . 2016-08-28 06:42 '16 at 6:42 am 2016-08-28 06:42

Peržiūrėkite kitus klausimus apie žymes arba Užduoti klausimą