Jest to pierwszy problem dotyczący wyszukiwania binarnego w Leetcode. Poprosimy o zwrot indeksu celu w danej tablicy. Moja pierwsza próba rozwiązania była następująca:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int result = -1;
        for(int i = 0; i < nums.size(); i++){
            if (nums[i] == target)
                result = i;
          
        }
        return result;
    }
};

Jeśli nie umiełem zwrotu wyników powrotu dwa razy, przekroczyłem komunikat czasu z jakiegoś powodu. W każdym razie, dla tablicy i celu poniżej tego kodu zwraca wartość nonsensową 16, gdy powinna powrócić 4:

[-1,0,3,5,9,12]
9

Omówiłem się z przyjacielem i wymyślił rozwiązanie w Pythonie w tym samym duchu:

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l = -1
        for i in nums:
            l += 1
            if i == target:
                print(l)
                return l

Ten pracował doskonale. Nie widzę, jak to różni się od jednego w C ++. Czy to w jakiś sposób związane z indeksami Python i C? Dlaczego rozwiązanie C ++ nie działa? Przepraszamy, jeśli są to wszystkie bardzo głupie pytania, jestem raczej nowy, aby programować ogólnie. Każda pomoc jest przyjęta przyjęta.

Edytuj: Naprawiłem stan pętli do i < nums.size(), którego wcześniej nie zauważyłem. To rozwiązuje czas przekroczony czas, który dostałem i pozwala mi umieścić zwrot poza pętli, jednak teraz otrzymuję wartość 6 z jakiegoś powodu.

Edytuj 2: Naprawiono oświadczenie if na result = i, rozwiązało wszystko. Kudos do oznaczenia za zauważenie tego bardzo głupiego błędu. Wszystko jest teraz dobre. Dziękuję wszystkim.

0
some1else2 25 październik 2020, 02:25

1 odpowiedź

Najlepsza odpowiedź
  • Wyjaśnia go na Wiki
  • Oto wyszukiwanie binarne w C ++:
// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();


// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>

using ValueType = std::uint_fast16_t;

static const struct Solution {
    static const int search(
        const std::vector<int>& nums,
        const int target
    ) {
        ValueType lo = 0;
        ValueType hi = std::size(nums) - 1;

        while (lo < hi) {
            ValueType mid = lo + (hi - lo) / 2;

            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid])) {
                lo = mid + 1;

            } else {
                hi = mid;
            }
        }

        return lo == hi && nums[lo] == target ? lo : -1;
    }
};

  • W Pythonie:
class Solution:
    def search(self, nums, target):
        if not nums:
            return -1
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] >= nums[lo]:
                if nums[lo] <= target <= nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if nums[mid] <= target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1
  • Oto jedno z oficjalnych rozwiązań LeetCode, a także komentował:
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        def find_rotate_index(left, right):
            if nums[left] < nums[right]:
                return 0
            
            while left <= right:
                pivot = (left + right) // 2
                if nums[pivot] > nums[pivot + 1]:
                    return pivot + 1
                else:
                    if nums[pivot] < nums[left]:
                        right = pivot - 1
                    else:
                        left = pivot + 1
                
        def search(left, right):
            """
            Binary search
            """
            while left <= right:
                pivot = (left + right) // 2
                if nums[pivot] == target:
                    return pivot
                else:
                    if target < nums[pivot]:
                        right = pivot - 1
                    else:
                        left = pivot + 1
            return -1
        
        n = len(nums)
        
        if n == 0:
            return -1
        if n == 1:
            return 0 if nums[0] == target else -1 
        
        rotate_index = find_rotate_index(0, n - 1)
        
        # if target is the smallest element
        if nums[rotate_index] == target:
            return rotate_index
        # if array is not rotated, search in the entire array
        if rotate_index == 0:
            return search(0, n - 1)
        if target < nums[0]:
            # search on the right side
            return search(rotate_index, n - 1)
        # search on the left side
        return search(0, rotate_index)

  • Python nie ma przepełnienia int (mid = start + (end - start) // 2). Oto kolejne oficjalne rozwiązanie LeetCode dla tego problemu:
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start, end = 0, len(nums) - 1
        while start <= end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] >= nums[start]:
                if target >= nums[start] and target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
            else:
                if target <= nums[end] and target > nums[mid]: 
                    start = mid + 1
                else:
                    end = mid - 1
        return -1
2
Emma 25 październik 2020, 01:10