Diberikan daftar angka dengan hanya 3 angka unik (1, 2, 3), urutkan daftar dalam waktu O(n). Selain itu, urutkan larik menggunakan spasi konstan O(1).

Contoh:

Input: [3, 3, 2, 1, 3, 2, 1]

Output: [1, 1, 2, 2, 3, 3, 3]

Di sini solusi yang saya buat (tidak ada ruang O(1) dan memiliki ruang kosong dalam array..): Apa fungsi ini sederhana .. meningkatkan ukuran susunan menjadi dua kali lipat jika semua elemennya adalah 2 ; Kemudian pergi ke panjang sebelumnya (arus/2) untuk mengurutkan elemen-elemennya .. jika 1 tidak apa-apa, jika menemukan 2 menempatkannya di panjang maksimum sebelumnya + 1, itu meningkatkan variabel len dan menghilangkan elemen dan jika 3 Dorong dan hapus elemen .. maka Anda memiliki ruang kosong dalam array dan Anda tidak memenuhi plus masalah tetapi O(n).

function sort(list) {
    let len = list.length;
    list.length=len*2
    for(let i=0; i<list.length/2; i++){
        let n=list[i]
        if(n==2){
            list[len]=n
            delete list[i]
            len++
        }else if(n==3){
            list.push(n)
            delete list[i]
        }
    }
    return list
}

console.log(sort([1,2,3,2,1,1]))
2
RazerJs 28 Oktober 2019, 16:35

5 jawaban

Jawaban Terbaik

Anda dapat menggunakan algoritme masalah bendera nasional Belanda:

Masalah bendera nasional Belanda 1 adalah masalah pemrograman ilmu komputer yang diajukan oleh Edsger Dijkstra (Dalam bab buku Disiplin Pemrograman Prentice-Hall, 1976). Bendera Belanda terdiri dari tiga warna: merah, putih, dan biru. Diberikan bola dari tiga warna ini yang disusun secara acak dalam satu garis (jumlah bola sebenarnya tidak masalah), tugasnya adalah mengaturnya sedemikian rupa sehingga semua bola dengan warna yang sama berkumpul dan kelompok warna kolektifnya berada dalam urutan yang benar.

var array = [3, 3, 2, 1, 3, 2, 1],
    MID = 2,
    i = 0,
    j = 0,
    n = array.length - 1;

while (j <= n) {
    if (array[j] < MID) {
        [array[i], array[j]] = [array[j], array[i]];
        i++;
        j++;
    } else if (array[j] > MID) {
        [array[n], array[j]] = [array[j], array[n]];
        n--;
    } else {
        j++;
    }
}

console.log(array);
11
Nina Scholz 28 Oktober 2019, 14:43

Saya mengikuti pendekatan bruteforce sederhana yang masih memberikan O(n) di akhir. Lagipula O(2N) + O(3) = O(N)

import sys

def sortNums(nums):
    res = {}
    mi = sys.maxsize
    ma = -1 * sys.maxsize
    mid = 0
    for i in nums: #O(n)
        if i in res:
            res[i] += 1
        else:
            res[i] = 1
        if mi > i:
            mi = i
        if ma < i:
            ma = i
    
    for ele in res.keys(): #O(3)
        if ele != mi and ele != ma:
            mid = ele

    return ([mi] * res[mi]) + ( [mid] * res[mid] ) + ([ma] * res[ma]) # O(n)

print(sortNums([3, 3, 2, 1, 3, 2, 1]))
# [1, 1, 2, 2, 3, 3, 3]
0
papaya 11 Januari 2021, 18:43

Menurut saya, Anda cukup menginisialisasi tiga variabel sebagai 0 untuk hitungan masing-masing 1, 2 dan 3. Lintasi array sekali dan tingkatkan penghitung yang sesuai dengan 1 untuk nilai di setiap indeks yaitu jika nilai pada indeks tertentu adalah 2, tambahkan variabel kedua dengan 1.

Setelah, Anda mendapatkan hitungan, indeks (Hitungan1 - 1) akan menjadi kemunculan terakhir dari 1, indeks (Hitung1 + Hitungan2 - 1) akan menjadi kemunculan terakhir dari 2 dan (Count1 + Count2 + Count3 - 1)th indeks akan menjadi kemunculan terakhir dari 3.

Anda dapat melintasi seluruh array dan menetapkan nilai yang sesuai. Cara ini agak mirip Menghitung Sortir tetapi tentu saja tidak stabil. Namun, Anda memiliki opsi lain seperti yang telah disebutkan dalam jawaban sebelumnya -Masalah Bendera Nasional Belanda

0
Pulkit Jatav 28 Oktober 2019, 16:06

Karena fakta bahwa Anda mengetahui bahwa larik hanya dapat berisi 3 item, Anda dapat mengulangi seluruh larik untuk setiap item, (ini berarti algoritme berjalan 3*n kali = O(3n) = O(n)).

Pembatasan ruang menunjukkan bahwa Anda harus bekerja di tempat, artinya, bekerja pada array input.

Ini solusi saya :]

function swap(i, j, arr) {
  const currentVal = arr[j];
  arr[j] = arr[i];
  arr[i] = currentVal;
}

function sort(arr) {
  let globalIndex = 0;
  [1, 2, 3].forEach(item => {
    for (let i = globalIndex; i < a.length; i++) {
      if (arr[i] === item) {
        swap(i, globalIndex, arr);
        globalIndex++;
      }
    }
  });
}

const a = [1, 2, 3, 2, 1, 1];

sort(a);

console.log(a);
2
felixmosh 28 Oktober 2019, 14:32

Anda dapat menghitung jumlah kemunculan 1, 2, 3 dan menggunakan info itu untuk membuat ulang/mendapatkan array yang diurutkan:

const arr = [3, 3, 2, 1, 3, 2, 1]

const count = arr.reduce((acc, curr) => {
  acc[curr]++;
  return acc;
}, {1: 0, 2: 0, 3: 0})

arr.forEach((_, j) => {
  if (j < count[1])
    arr[j] = 1
  else if (j < count[1] + count[2])
    arr[j] = 2
  else
    arr[j] = 3
})

console.log(arr)
2
El Aoutar Hamza 28 Oktober 2019, 14:24