Check if an Array Is Sorted

Q: Apakah array dengan elemen yang sama sudah terurut?

Dalam urutan tidak menurun, ya: [4, 4, 4] sudah terurut karena tidak ada elemen yang lebih besar daripada elemen berikutnya. Jika suatu soal meminta urutan yang meningkat secara ketat, ubah pemeriksaannya agar juga menolak elemen bertetangga yang nilainya sama.

PemulaArray dan string

+10

Kamu mendapatkan array bilangan bulat nums. Kembalikan true jika array tersebut tersusun dalam urutan tidak menurun, artinya setiap elemen lebih kecil dari atau sama dengan elemen setelahnya, dan false jika tidak. Elemen bersebelahan yang sama tidak masalah: [2, 2, 3] dianggap sudah terurut. Array dengan satu elemen sudah terurut.

Fungsi

isSorted(nums: integer-array) → boolean

numsinteger-array: array bilangan bulat yang akan diperiksa
Mengembalikanboolean: benar jika setiap elemen kurang dari atau sama dengan elemen berikutnya, salah jika tidak

Batasan

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Contoh

Input: nums = [1, 3, 3, 7]
Output: true
Penjelasan: Setiap langkah naik atau tetap sama: 1 ke 3, 3 ke 3, 3 ke 7. Angka 3 yang berulang diperbolehkan, jadi jawabannya adalah true.

Pertanyaan lanjutan

Bagaimana kamu memeriksa array yang mungkin diurutkan ke arah mana pun, menaik atau menurun, hanya dalam satu kali lintasan?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Array terurut tepat ketika tidak ada elemen yang lebih besar daripada elemen tepat setelahnya. Jadi, satu kali penelusuran terhadap n-1 pasangan yang bersebelahan dapat menentukan hal ini, dan penelusuran bisa berhenti pada penurunan pertama.

Urutkan salinan dan bandingkan

Intuisi

Array yang sudah terurut adalah array yang tidak berubah setelah diurutkan: urutkan salinannya, lalu bandingkan dengan nums posisi demi posisi. Untuk [2, 5, 4, 9], salinannya [2, 4, 5, 9] berbeda pada posisi 1, jadi jawabannya adalah false.

Pengurutan membutuhkan O(n log n), sekitar 6 × 10^4 perbandingan untuk 5000 angka, ditambah memori O(n) untuk salinannya, dan membaca seluruh array meskipun pasangan pertama sudah tidak berurutan.

Algoritma

Salin nums agar data asli tetap tidak berubah.
Urutkan salinannya berdasarkan urutan angka dari yang terkecil.
Bandingkan salinannya dengan nums posisi demi posisi.
Kembalikan true jika setiap posisi cocok, jika tidak kembalikan false.

def isSorted(nums):
    # sorted returns a new list, so nums itself is left as it was.
    return sorted(nums) == nums

Bandingkan setiap pasangan tetangga

Intuisi

Karena ≤ bersifat berantai (a ≤ b dan b ≤ c menghasilkan a ≤ c), n-1 pasangan posisi yang bersebelahan mencakup setiap pasangan posisi, dan array yang tidak terurut selalu memiliki pasangan bersebelahan yang nilainya menurun. Jadi, telusuri i dari 1 hingga n-1 dan kembalikan false saat pertama kali menemukan nums[i-1] > nums[i]. Untuk [2, 5, 4, 9], pasangan itu adalah (5, 4), dan 9 tidak pernah dibaca. Nilai bersebelahan yang sama lolos, karena hanya > yang menyebabkan kegagalan.

Setiap pasangan dibandingkan satu kali: waktu O(n) dan memori O(1).

Algoritma

Lakukan perulangan i dari 1 hingga n-1.
Jika nums[i-1] > nums[i], kembalikan false.
Jika perulangan selesai, kembalikan true. Satu elemen akan melewati perulangan dan sudah terurut.

def isSorted(nums):
    for i in range(1, len(nums)):
        # One step down anywhere breaks the order.
        if nums[i - 1] > nums[i]:
            return False
    return True

Jebakan dan kasus tepi

Menganggap elemen bersebelahan yang nilainya sama sebagai kegagalan. Pengujian nums[i-1] >= nums[i] menolak [1, 3, 3, 7].
Membaca melewati akhir array. Perulangan dari 0 hingga n-1 yang membandingkan nums[i] dengan nums[i+1] membaca di luar array pada langkah terakhir. Mulai dari i = 1 dan bandingkan dengan i-1.
Mengurangkan nilai alih-alih membandingkannya. nums[i] - nums[i-1] >= 0 menyebabkan overflow pada int 32-bit untuk [-1000000000, 1000000000]: 2 × 10^9 berubah menjadi negatif dan array dilaporkan tidak terurut. Comparator qsort yang ditulis sebagai x - y mengalami masalah yang sama.
Mengurutkan angka sebagai teks. Di JavaScript, sort() tanpa fungsi pembanding menempatkan 10 sebelum 9, sehingga hasil pengurutan dan perbandingan menjadi salah.

Pertanyaan yang sering diajukan3

Bagaimana cara memeriksa apakah sebuah array sudah terurut?

Bandingkan setiap elemen dengan elemen berikutnya. Jika ada elemen yang lebih besar daripada elemen di sebelah kanannya, array belum terurut dan kamu bisa berhenti. Jika kamu mencapai akhir tanpa menemukannya, berarti array sudah terurut. Proses ini membutuhkan waktu O(n) dan ruang tambahan O(1).

Apakah array dengan elemen yang sama sudah terurut?

Dalam urutan tidak menurun, ya: [4, 4, 4] sudah terurut karena tidak ada elemen yang lebih besar daripada elemen berikutnya. Jika suatu soal meminta urutan yang meningkat secara ketat, ubah pemeriksaannya agar juga menolak elemen bertetangga yang nilainya sama.

Bisakah saya mengurutkan salinan dan membandingkannya dengan yang asli?

Ya, ini memberikan jawaban yang benar, tetapi membutuhkan waktu O(n log n) dan memori ekstra O(n). Pemeriksaan tetangga tidak memerlukan salinan dan bisa berhenti pada langkah turun pertama.

def isSorted(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

nums = [1, 3, 3, 7]

Output yang diharapkan

true