Bagaimana untuk Mencari Nombor Terdekat dalam Senarai Integer?

Mencari Nombor Terhampir dengan Nilai Diberi dalam Senarai Integer

Andaikan kita mempunyai senarai integer dan ingin menentukan nombor yang mana paling hampir dengan nilai tertentu. Kami boleh menggunakan pelbagai kaedah untuk mencapainya.

Menggunakan Fungsi min() untuk Senarai Tidak Diisih:

Jika kami tidak dapat menjamin bahawa senarai itu diisih, kami boleh memanfaatkan fungsi min() terbina dalam. Ia memilih elemen dengan jarak minimum daripada nombor yang ditentukan menggunakan fungsi kekunci.

>>> min(myList, key=lambda x:abs(x-myNumber))
4

Kaedah ini cekap mencari nombor terdekat dalam kerumitan masa O(n).

Menggunakan Kaedah Pembahagian Dua untuk Senarai Isih:

Jika senarai sudah diisih, atau kami sanggup mengisihnya sekali, kami boleh menggunakan kaedah pembahagian dua. Kaedah ini mengurangkan kerumitan masa kepada O(log n). Walau bagaimanapun, menyemak sama ada senarai telah diisih mengambil O(n), dan mengisih sendiri memerlukan O(n log n).

>>> low, high = 0, len(myList) - 1
>>> while low <= high:
>>>     mid = (low + high) // 2
>>>     if myList[mid] == myNumber:
>>>         return myList[mid]
>>>     elif myList[mid] > myNumber:
>>>         high = mid - 1
>>>     else:
>>>         low = mid + 1
>>>     if low > high:
>>>         closest = myList[high] if abs(myList[high] - myNumber) < abs(myList[low] - myNumber) else myList[low]
>>>         return closest

Dengan memilih elemen yang paling hampir, kaedah ini menyediakan penyelesaian optimum untuk senarai diisih .

Atas ialah kandungan terperinci Bagaimana untuk Mencari Nombor Terdekat dalam Senarai Integer?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!