Longest Consecutive Sequence

Q: Berapa kompleksitas waktu dari Longest Consecutive Sequence?

Solusi dengan hash set berjalan dalam waktu rata-rata O(n) dengan memori tambahan O(n) . Pengurutan dan penghitungan membutuhkan waktu O(n log n) . Mencari array untuk setiap nilai berikutnya tanpa set membutuhkan waktu hingga O(n³) .

SedangHashing

+10

Kamu mendapatkan array bilangan bulat nums yang tidak memiliki urutan tertentu. Urutan berurutan adalah sekumpulan nilai x, x+1, x+2, dan seterusnya, yang masing-masing muncul di suatu tempat dalam nums. Kembalikan panjang urutan berurutan terpanjang. Nilai yang muncul lebih dari sekali dihitung satu kali.

Fungsi

longestConsecutive(nums: integer-array) → integer

numsinteger-array: bilangan bulat, dalam urutan apa pun, boleh berulang
Mengembalikaninteger: panjang rentetan terpanjang dari nilai berurutan yang terdapat dalam nums

Batasan

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Nilai dapat berulang. Posisi dalam array tidak penting, yang penting hanya nilai mana yang ada.

Contoh

Input: nums = [40, 4, 39, 1, 3, 2, 41]
Output: 4
Penjelasan: 1, 2, 3, dan 4 semuanya ada, membentuk rangkaian berisi 4 angka, meskipun tersebar di dalam array. Rangkaian lainnya, dari 39 hingga 41, hanya memiliki 3 nilai.

Input: nums = [7, 3, 7, 5, 6, 5]
Output: 3
Penjelasan: 5, 6, dan 7 membentuk deretan 3. 7 kedua dan 5 kedua tidak menambahkan apa pun, dan 3 tidak bisa bergabung karena 4 tidak ada.

Pertanyaan lanjutan

Misalkan nilai datang satu per satu dan setelah setiap nilai kamu harus melaporkan perulangan terpanjang sejauh ini. Bisakah kamu menjaga jawaban tetap terkini dalam waktu rata-rata O(1) per nilai?

Petunjuk

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

0 dari 3 dibuka

Solusi

Nilai-nilai dalam suatu rangkaian bisa berada di mana saja dalam array. Pengurutan menyusunnya dalam O(n log n). Hash set menjawab pertanyaan "apakah x+1 ada di sini?" dalam O(1), dan jika kamu hanya menghitung dari nilai-nilai yang x-1-nya tidak ada, setiap nilai dilewati satu kali: totalnya O(n).

Hitung maju dari setiap nilai dengan menelusuri array

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Anggap setiap nilai sebagai kemungkinan awal sebuah perulangan. Dari x, cari x+1 di dalam array, lalu x+2, sampai suatu nilai tidak ditemukan, lalu pertahankan hitungan terpanjang. Setiap perulangan memiliki nilai terkecil di nums, dan perulangan menelusuri seluruh rangkaian darinya.

Setiap pencarian membaca hingga n nilai, dan perulangan panjang ditelusuri kembali dari setiap anggotanya. Untuk 10^4 nilai yang membentuk satu rangkaian acak, penelusuran membutuhkan sekitar n²/2 = 5 × 10^7 langkah, dengan setiap pemindaian memeriksa rata-rata setengah array: sekitar 2.5 × 10^11 perbandingan.

Algoritma

Tetapkan best ke 0.
Untuk setiap nilai start dalam nums, tetapkan current ke start dan length ke 1.
Selama pemindaian nums menemukan current+1, tambahkan 1 ke current dan length.
Simpan length ke dalam best jika nilainya lebih besar.
Kembalikan best.

def longestConsecutive(nums):
    best = 0
    for start in nums:
        current = start
        length = 1
        # "in" on a list reads it from the front until it finds the value.
        while current + 1 in nums:
            current += 1
            length += 1
        best = max(best, length)
    return best

Urutkan, lalu hitung rangkaian

Intuisi

Pengurutan menempatkan nilai-nilai dari setiap perulangan secara berdampingan: [40, 4, 39, 1, 3, 2, 41] menjadi [1, 2, 3, 4, 39, 40, 41], lalu perulangan dibaca dari kiri ke kanan.

Telusuri nilai-nilai yang sudah diurutkan dan simpan panjang perulangan saat ini. Nilai yang lebih besar satu dari nilai sebelumnya akan memperpanjangnya. Nilai yang berulang tidak memperpanjang atau mengakhiri perulangan, jadi lewati nilai itu. Nilai lainnya memulai perulangan baru dengan panjang 1.

Pengurutan memerlukan biaya O(n log n) dan penelusuran memerlukan biaya O(n). Pengurutan di tempat tidak memerlukan array tambahan; bahasa yang mengurutkan salinan menggunakan memori O(n).

Algoritma

Urutkan nums dalam urutan menaik.
Tetapkan best dan run ke 1, karena array tidak pernah kosong.
Untuk setiap indeks i mulai dari 1, lewati nums[i] jika nilainya sama dengan nums[i-1].
Jika nums[i] adalah nums[i-1]+1, tambahkan 1 ke run; jika tidak, tetapkan run ke 1. Simpan run dalam best jika nilainya lebih besar.
Kembalikan best.

def longestConsecutive(nums):
    nums.sort()
    best = 1
    run = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            continue  # a repeat neither extends nor breaks the run
        if nums[i] == nums[i - 1] + 1:
            run += 1
        else:
            run = 1
        best = max(best, run)
    return best

Hash set, menghitung hanya dari awal setiap perulangan

Intuisi

Untuk setiap nilai dalam hash set, pemeriksaan keanggotaan memerlukan biaya rata-rata O(1), dan nilai yang berulang digabungkan menjadi satu entri.

Menelusuri dari setiap nilai tetap akan mengulangi pekerjaan: dalam rangkaian 1, 2, 3, 4, kamu akan menempuh 3 langkah dari 1, 2 langkah dari 2, dan 1 langkah dari 3. Jadi, telusuri hanya dari nilai pertama dalam suatu rangkaian, yaitu nilai x yang x-1 tidak ada. Dalam contoh 1, hanya 1 dan 39 yang memenuhi syarat, sehingga menghasilkan rangkaian dengan panjang 4 dan 3.

Setiap nilai termasuk dalam satu rangkaian dan hanya dilalui oleh penelusuran rangkaian tersebut, sehingga seluruh penelusuran paling banyak menempuh n langkah. Dengan satu pemeriksaan untuk setiap nilai, total waktunya O(n) dan penggunaan memorinya O(n) untuk set tersebut.

Algoritma

Masukkan setiap nilai dari nums ke dalam hash set values, lalu atur best ke 0.
Untuk setiap nilai x dalam set tersebut, lewati jika x-1 ada di dalam set: nilai itu bukan nilai pertama dalam deretnya.
Jika tidak, atur end ke x dan tambahkan 1 selama end+1 ada di dalam set.
Simpan end-x+1 ke dalam best jika nilainya lebih besar.
Kembalikan best.

def longestConsecutive(nums):
    values = set(nums)
    best = 0
    for value in values:
        # Only a value with no left neighbour starts a run.
        if value - 1 in values:
            continue
        end = value
        while end + 1 in values:
            end += 1
        best = max(best, end - value + 1)
    return best

Jebakan dan kasus tepi

Menganggap nilai yang berulang sebagai celah atau langkah setelah pengurutan. Dalam [1, 2, 2, 3], mengatur ulang rangkaian pada 2 kedua menghasilkan 2, sedangkan menghitungnya sebagai langkah menghasilkan 4. Jawabannya adalah 3.
Memulai best dari 0 dalam penelusuran terurut dan hanya memperbaruinya di dalam perulangan. Array yang berisi satu nilai akan menghasilkan 0, bukan 1.
Menelusuri setiap nilai dalam set, bukan hanya awal rangkaian. Satu rangkaian yang terdiri dari 10^4 nilai membutuhkan 5 × 10^7 langkah.
Melakukan perulangan pada nums, bukan pada set. Jika nilai pertama dari rangkaian berisi 2.500 nilai muncul sebanyak 2.000 kali, rangkaian tersebut ditelusuri 2.000 kali.
Mengindeks array berdasarkan nilai. Nilainya mencapai ±10^9, jadi diperlukan 2 × 10^9 entri.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Longest Consecutive Sequence?

Solusi dengan hash set berjalan dalam waktu rata-rata O(n) dengan memori tambahan O(n). Pengurutan dan penghitungan membutuhkan waktu O(n log n). Mencari array untuk setiap nilai berikutnya tanpa set membutuhkan waktu hingga O(n³).

Bisakah kamu menyelesaikan Urutan Berurutan Terpanjang tanpa memori tambahan?

Ya, jika kamu boleh mengurutkan ulang input: urutkan langsung di tempat dan hitung kelompok dalam satu lintasan, dengan melewati pengulangan. Cara ini menggunakan memori tambahan O(1), tetapi membutuhkan waktu O(n log n). Solusi O(n) membutuhkan hash set.

Bisakah union-find menyelesaikan Longest Consecutive Sequence?

Ya. Jadikan setiap nilai yang berbeda sebagai set, gabungkan x dengan x+1 jika keduanya ada, lalu kembalikan ukuran set terbesar. Algoritma ini berjalan dalam waktu mendekati O(n), tetapi memerlukan pemetaan nilai ke indeks, tautan parent, dan ukuran, sedangkan penelusuran hash set hanya memerlukan satu set.

def longestConsecutive(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [40, 4, 39, 1, 3, 2, 41]

Output yang diharapkan

Longest Consecutive Sequence

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Hitung maju dari setiap nilai dengan menelusuri array

Urutkan, lalu hitung rangkaian

Hash set, menghitung hanya dari awal setiap perulangan

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa