Saya seharusnya mengurutkan daftar angka, tapi saya sangat malas. Sangat sulit untuk mencari cara menukar semua angka di sekitar sampai semuanya dalam urutan meningkat, jadi saya datang dengan algoritma saya sendiri yang akan menjamin bahwa daftar baru diurutkan¹. Begini cara kerjanya:
Untuk daftar ukuran N , kita perlu iterasi N-1 . Pada setiap iterasi,
Periksa apakah nomor ke- N lebih kecil dari nomor ke-1. Jika ya, maka kedua angka ini sudah diurutkan, dan kita dapat melewati iterasi ini.
Jika tidak, maka Anda harus terus mengurangi angka N pertama hingga kedua angka ini berurutan.
Mari kita ambil contoh konkret. Katakanlah input tadi
10 5 7 6 1
Pada iterasi pertama, kami akan membandingkan 10 dan 5. 10 lebih besar dari 5, jadi kami menurunkannya hingga lebih kecil:
4 5 7 6 1
Sekarang kita membandingkan 5 dan 7. 5 lebih kecil dari 7, jadi kita tidak perlu melakukan apa pun pada iterasi ini. Jadi kita pergi ke yang berikutnya dan membandingkan 7 dan 6. 7 lebih besar dari 6, jadi kami mengurangi tiga angka pertama sampai lebih kecil dari 6, dan kami mendapatkan ini:
2 3 5 6 1
Sekarang kita membandingkan 6 dan 1. Sekali lagi, 6 lebih besar dari 1, jadi kita mengurangi empat angka pertama sampai lebih kecil dari 1, dan kita mendapatkan ini:
-4 -3 -1 0 1
Dan kita selesai! Sekarang daftar kami dalam urutan sempurna. Dan, untuk membuat segalanya lebih baik, kami hanya perlu mengulangi daftar N-1 kali, jadi algoritma ini mengurutkan daftar dalam waktu O (N-1) , yang saya cukup yakin adalah algoritma tercepat yang ada.²
Tantangan Anda untuk hari ini adalah mengimplementasikan Sort Malas ini. Program atau fungsi Anda akan diberi array bilangan bulat dalam format standar apa pun yang Anda suka, dan Anda harus melakukan sortir malas ini dan mengembalikan daftar " sortir " yang baru . Array tidak akan pernah kosong atau mengandung non-integer.
Berikut ini beberapa contohnya:
Input: 10 5 7 6 1
Output: -4 -3 -1 0 1
Input: 3 2 1
Output: -1 0 1
Input: 1 2 3
Output: 1 2 3
Input: 19
Output: 19
Input: 1 1 1 1 1 1 1 1 1
Output: -7 -6 -5 -4 -3 -2 -1 0 1
Input: 5 7 11 6 16 2 9 16 6 16
Output: -27 -25 -21 -20 -10 -9 -2 5 6 16
Input: -8 17 9 7
Output: -20 5 6 7
Seperti biasa, ini kode-golf , jadi tulislah program sesingkat mungkin!
¹ Ini tidak berarti seperti apa artinya, tetapi secara teknis itu benar
² Saya benar-benar bercanda, tolong jangan benci saya
sumber
<sarcasm>
Algoritma pengurutan ini sebenarnya masihO(N^2)
memiliki kompleksitas waktu karena Anda harus memeriksa semua item yang sebelumnya diakses pada daftar untuk mengurangi mereka. Saya sarankan menelusuri daftar mundur sebagai gantinya dan mengurangi hanya satu nomor per langkah yang diperlukan. Ini akan memberi AndaO(N)
kompleksitas sejati !</sarcasm>
O(n^2)
dalam hal akses memori, tetapi bukankah ituO(n)
untuk perbandingan?O(N^2)
.Jawaban:
Jelly ,
14 12 119 byte-2 byte berkat ETHproductions (gunakan angka minimum,
«
)Tautan monadik yang mengambil dan mengembalikan daftar bilangan bulat.
Cobalah online! atau lihat test suite .
Saya benar-benar tidak berpikir ini cukup Malas ™!
Bagaimana?
sumber
Haskell , 40 byte
Cobalah online!
sumber
JavaScript (ES6), 61 byte
Uji kasus
Tampilkan cuplikan kode
sumber
Jelly , 12 byte
Cobalah online!
Bagaimana itu bekerja
Ide dasar yang dimainkan adalah ini: Jika Anda membalikkan array input dan output, output hanyalah input dengan setiap delta 0 atau lebih besar diganti dengan -1. Sebagai contoh:
sumber
k, 20 byte
Cobalah online.
Penjelasan:
sumber
Haskell, 56 byte
Cobalah online!
Simpan bagian pertama dari daftar di parameter
a
. Pada setiap langkah, tambahkan elemen berikutnyax
ke akhira
dan tingkatkan semua elemen dengan minimum(y-x-1)
dan0
.sumber
Python , 54 byte
Cobalah online!
Mengambil input seperti splatted
f(1,2,3)
. Menghasilkan daftar. Menggunakan waktu eksponensial.sumber
C #, 76 byte
Ini mengubah daftar di tempat. Itu berjalan melalui daftar mundur dan menjaga total berjalan delta untuk diterapkan ke setiap nomor.
sumber
JavaScript (ES6), 59 byte
sumber
f=
untuk jawaban JS untuk menyimpan dua bytef(a)
) sehingga masih membutuhkan nama.Brain-Flak , 153 byte
Cobalah online!
Ini termasuk
+1
untuk-r
bendera.sumber
R, 56 byte
function(s){s-c(rev(cumsum(rev(pmax(0,-diff(s)+1)))),0)}
sumber
diff
, saya mencoba mencari cara untuk mendapatkan itu bekerja ... Ngomong-ngomong, Anda dapat menyingkirkan kawat gigi di sekitar fungsi tubuh untuk -2 byte, tetapi lebih baik lagi, Anda dapat menggunakans=scan()
alih-alih fungsi definisi untuk menyimpan beberapa byte lagi. Akan lebih bagus jika Anda menyertakan tautan ke Coba online sehingga orang lain dapat memverifikasi bahwa kode ini berfungsi untuk semua kasus uji.JavaScript (ES6), 68 byte
Input dan output adalah array bilangan bulat.
Cuplikan Tes
sumber
JavaScript (ES6), 50 byte
Penjelasan:
Ini adalah solusi rekursif, yang pertama mengkloning array, kemudian menurunkan semua nilai hingga elemen lebih besar atau sama dengan elemen berikutnya dalam array.
Fungsi ini memanggil dirinya sendiri selama elemen-elemennya rusak. Ketika elemen akhirnya diurutkan, klon dikembalikan. (Kami tidak dapat mengembalikan array itu sendiri, karena
some()
metode ini akan mengurangi semua elemennya, membuat semuanya menjadi -1.)Kasus uji:
sumber
SWI-Prolog, 194 byte
Mungkin dapat mencobanya online di sini: http://swish.swi-prolog.org/p/LazySort.pl
Anda bertanya
l(L, [10,5,7,6,1]).
yang mengatakan "selesaikan untuk L, di mana L adalah versi malas diurutkan dari daftar ini".Dua fungsi tersebut adalah:
l
azysorted (A, B) - menyatakan bahwa A adalah versi lazysorted dari B, jika keduanya daftar kosong, atau jika A dapat diperoleh dengan membalikkan B, memanggil fungsi penolong untuk berjalan dalam daftar dan melakukan pengurangan dengan akumulator. mendorong setiap nilai lebih rendah dari yang sebelumnya, dan membalikkan hasilnya kembali ke jalan yang benar.f
helper cocok dengan dua daftar, nilai angka sebelumnya dalam daftar, dan akumulator perbedaan bergulir, dan memecahkan nilai baru dari posisi daftar saat ini menjadi nilai asli dikurangi akumulator perbedaan, secara opsional dikurangi nilai baru yang diperlukan untuk memaksa ini nilai di bawah angka sebelumnya dalam daftar, danf
harus menyelesaikan untuk ekor daftar secara rekursif dengan akumulator perbedaan sekarang meningkat.Cuplikan layar kasus uji pada Swish:
sumber
JavaScript (ES6), 61 byte
Bukan solusi terpendek tapi saya tidak bisa melewatkan kesempatan untuk menggunakannya
reduceRight
.sumber
C # (.NET Core) ,
89 88 8679 bytefor
s.Cobalah online!
Pertama
for
iterasi melalui array, lalu menghitung penurunan dan akhirnya elemen keduafor
mengurangi elemen jika perlu sampaii
posisi th.Apakah valid untuk hanya memodifikasi array asli daripada mengembalikan yang baru (masih terbiasa dengan aturan)?
sumber