Summary Ranges

Q: Apa kompleksitas waktu dari Summary Ranges?

O(n) . Setiap nilai dikunjungi satu kali, dan setiap rentang ditulis satu kali. Selain list output, ruang tambahan adalah O(1) : awal rentang saat ini dan satu atau dua indeks.

MudahInterval Array dan string

+10

Kamu mendapatkan array nums berisi bilangan bulat berbeda yang sudah diurutkan. Pisahkan array tersebut menjadi rentang bilangan bulat berurutan sesedikit mungkin, sehingga setiap nilai termasuk tepat dalam satu rentang. Tulis rentang a..b sebagai teks "a->b", atau sebagai "a" jika rentang tersebut berisi satu nilai. Kembalikan rentang dalam urutan menaik.

Fungsi

summaryRanges(nums: integer-array) → string-array

numsinteger-array: array bilangan bulat unik yang sudah diurutkan
Mengembalikanstring-array: rentang sebagai teks, dari nilai terkecil hingga terbesar

Batasan

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums diurutkan secara menaik dan tidak memiliki duplikat.

Contoh

Input: nums = [0, 1, 2, 5, 6, 9]
Output: ["0->2", "5->6", "9"]
Penjelasan: 0, 1, 2 berurutan, jadi membentuk "0->2". Lompatan dari 2 ke 5 memulai rentang baru, "5->6", dan 9 berdiri sendiri sebagai "9".

Input: nums = [-3, -1, 0, 1, 4, 7, 8]
Output: ["-3", "-1->1", "4", "7->8"]
Penjelasan: -3 tidak memiliki tetangga (-2 tidak ada), -1, 0, 1 membentuk deretan, 4 berdiri sendiri, dan 7, 8 mengakhiri daftar. Nilai negatif bekerja dengan cara yang sama: -1 diikuti oleh -1 + 1 = 0.

Pertanyaan lanjutan

Misalkan nums bisa berisi nilai duplikat, seperti [1, 2, 2, 3]. Apa yang akan kamu ubah agar tetap mencetak "1->3"?

Petunjuk

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

0 dari 3 dibuka

Solusi

Karena nilainya diurutkan dan berbeda, rentang bilangan bulat berurutan merupakan rangkaian elemen bertetangga dalam array, dan berakhir tepat saat dua elemen bertetangga memiliki selisih lebih dari 1. Tidak ada rentang yang dapat melewati celah seperti itu, jadi pemisahan di setiap celah menghasilkan jumlah rentang paling sedikit.

Periksa kedua tetangga setiap nilai

Intuisi

Sebuah rentang dimulai pada nilai pertama, atau pada nilai yang tetangga kirinya bukan satu kurang. Rentang berakhir pada nilai terakhir, atau pada nilai yang tetangga kanannya bukan satu lebih. Dalam [0, 1, 2, 5, 6, 9], rentang dimulai pada 0, 5, dan 9, lalu berakhir pada 2, 6, dan 9.

Ingat nilai tempat rentang saat ini dimulai. Saat rentang berakhir pada nums[i], tulis "start->nums[i]", atau hanya "start" jika rentang dimulai dan berakhir pada nilai yang sama, seperti 9.

Setiap nilai memeriksa kedua tetangganya satu kali: waktu O(n), dan satu nilai awal yang diingat untuk ruang ekstra O(1).

Algoritma

Tetapkan start = nums[0].
Untuk setiap indeks i: jika i > 0 dan nums[i] != nums[i-1] + 1, tetapkan start = nums[i].
Jika i adalah indeks terakhir atau nums[i+1] != nums[i] + 1, rentang berakhir di sini.
Tambahkan "start" jika start == nums[i], jika tidak, tambahkan "start->nums[i]".
Kembalikan list setelah indeks terakhir.

def summaryRanges(nums):
    n = len(nums)
    ranges = []
    start = nums[0]
    for i in range(n):
        # A range opens where the value before is not one less.
        if i > 0 and nums[i] != nums[i - 1] + 1:
            start = nums[i]
        # A range closes where the value after is not one more.
        if i == n - 1 or nums[i + 1] != nums[i] + 1:
            ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
    return ranges

Dua pointer untuk setiap kelompok

Intuisi

Temukan kedua ujung setiap rentang. Pointer i berada pada nilai pertamanya. Pointer j dimulai dari i dan bergerak ke kanan selama nilai berikutnya tepat satu lebih besar, sehingga berhenti pada nilai terakhir. Lalu i melompat ke j+1.

Untuk [-3, -1, 0, 1, 4, 7, 8]: pada -3, nilai berikutnya -1 bukan -2, sehingga "-3" berdiri sendiri. Dari -1, j bergerak melewati 0 dan 1 lalu berhenti sebelum 4: "-1->1". Berikutnya adalah "4" dan "7->8".

Kedua pointer hanya bergerak maju, jadi perulangan bagian dalam berjalan sebanyak n kali secara total: waktu O(n) dan ruang ekstra O(1).

Algoritma

Tetapkan i = 0.
Tetapkan j = i, lalu geser j ke kanan selama j+1 < n dan nums[j+1] == nums[j] + 1.
Tambahkan "nums[i]" jika i == j, jika tidak, tambahkan "nums[i]->nums[j]".
Tetapkan i = j + 1 dan ulangi sampai i
Kembalikan list.

def summaryRanges(nums):
    ranges = []
    n = len(nums)
    i = 0
    while i < n:
        # i is the first value of a run; push j to its last value.
        j = i
        while j + 1 < n and nums[j + 1] == nums[j] + 1:
            j += 1
        ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
        # The next run starts right after this one.
        i = j + 1
    return ranges

Jebakan dan kasus tepi

Lupa menuliskan rentang terakhir. Perulangan yang menulis rentang hanya saat menemukan celah tidak pernah menulis rentang terakhir, sehingga [0, 1, 2, 5, 6, 9] kehilangan "9". Tutup rentang juga pada indeks terakhir.
Menulis "a->a" untuk satu nilai. Rentang yang terdiri dari satu nilai ditulis sebagai "a".
Menampilkan nilai besar dalam notasi ilmiah. R mengubah double seperti 1000000000 menjadi 1e+09; ubah nilainya menjadi integer sebelum menempelkannya.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Summary Ranges?

O(n). Setiap nilai dikunjungi satu kali, dan setiap rentang ditulis satu kali. Selain list output, ruang tambahan adalah O(1): awal rentang saat ini dan satu atau dua indeks.

Bagaimana cara menangani rentang yang hanya memiliki satu angka?

Periksa apakah rentang dimulai dan berakhir pada nilai yang sama. Jika ya, tulis nilai itu saja, seperti "9". Jika tidak, tulis nilai awal, panah, lalu nilai akhir, seperti "5->6". Dengan dua pointer, pengujiannya adalah i == j.

Apakah Summary Ranges memerlukan input yang sudah diurutkan?

Ya. Method ini hanya membandingkan nilai yang bersebelahan, jadi cara ini mengandalkan bilangan bulat berurutan yang terletak berdampingan. Untuk input yang belum diurutkan, urutkan terlebih dahulu, sehingga tugas ini menjadi O(n log n), atau masukkan nilai-nilainya ke dalam hash set dan kembangkan setiap rentang mulai dari nilai terkecilnya, seperti pada masalah deret berurutan terpanjang.

def summaryRanges(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

nums = [0, 1, 2, 5, 6, 9]

Output yang diharapkan

["0->2", "5->6", "9"]