Bagaimana untuk Membandingkan Senarai Objek Tidak Tertib dengan Cekap?

Perbandingan Cekap Senarai Tidak Tersusun

Membandingkan senarai tidak tersusun, juga dikenali sebagai beg, boleh menjadi tugas yang mencabar, terutamanya apabila bekerja dengan objek dan bukannya jenis data ringkas seperti integer . Berikut ialah tiga pendekatan cekap untuk menangani masalah ini:

1. Kaedah Kaunter (O(n))

Untuk objek yang boleh dicincang (iaitu, boleh ditukar kepada nilai cincang yang unik), kaedah Counter() daripada modul koleksi Python boleh digunakan. Ia mencipta objek seperti kamus di mana kunci ialah elemen senarai dan nilai adalah kiraan masing-masing. Membandingkan dua senarai menggunakan pendekatan ini mempunyai kerumitan masa linear O(n), dengan n ialah panjang senarai.

import collections

def compare(s, t):
    return collections.Counter(s) == collections.Counter(t)

2. Kaedah Isih (O(n log n))

Jika objek dalam senarai adalah setanding (iaitu, ia mempunyai susunan yang ditentukan), mengisih senarai boleh menyediakan mekanisme perbandingan yang cekap. Kaedah sorted() dalam Python menyusun elemen dalam senarai, menjadikannya mudah untuk menentukan sama ada kedua-dua senarai mengandungi elemen yang sama dalam sebarang susunan. Pendekatan ini mempunyai kerumitan masa O(n log n), dengan n ialah panjang senarai.

def compare(s, t):
    return sorted(s) == sorted(t)

3. Perbandingan Kesaksamaan (O(n * n))

Jika objek tidak boleh dicincang dan tidak boleh diatur, pendekatan yang mudah ialah melakukan perbandingan kesaksamaan antara elemen kedua-dua senarai. Untuk setiap elemen dalam senarai pertama, kami mengeluarkannya daripada senarai kedua. Jika mana-mana elemen dalam senarai pertama tidak ditemui dalam senarai kedua, perbandingan gagal. Pendekatan ini mempunyai kerumitan masa terburuk O(n * n), dengan n ialah panjang senarai.

def compare(s, t):
    t = list(t)  # make a mutable copy
    try:
        for elem in s:
            t.remove(elem)
    except ValueError:
        return False
    return not t

Dengan menggunakan teknik perbandingan yang cekap ini, anda boleh membandingkan senarai objek yang tidak tertib dengan berkesan , sama ada ia boleh dicincang, boleh dipesan atau tidak.

Atas ialah kandungan terperinci Bagaimana untuk Membandingkan Senarai Objek Tidak Tertib dengan Cekap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!