Как работает эта программа? Как работает метод firstGreaterEqual - PullRequest
Новая
       8

Как работает эта программа? Как работает метод firstGreaterEqual

0 голосов
/ 23 июня 2018

Я новичок в переполнении стека. Я надеюсь, что этот вопрос соответствует руководящим принципам. Thnakyou.! 

     class Solution:
        def searchRange(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            start = self.firstGreaterEqual(nums, target)
            if start==len(nums) or nums[start]!=target:
                return [-1, -1]
            return [start, self.firstGreaterEqual(nums, target+1)-1]
        def firstGreaterEqual(self, nums, target):
            lo, hi = 0, len(nums)
            while lo<hi:
                mid = (hi+lo)//2
                if nums[mid]<target:
                    lo = mid + 1
                else:
                    hi = mid
            return lo


    Input: nums = [5,7,7,8,8,10], target = 6
    Output: [-1,-1]

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Эта программа предназначена для поиска диапазона ссылка на программу Это решение имеет лучшее время выполнения. Мне трудно понять логику этого. Он использует бинарный поиск, но я не до конца его понимаю.

1 Ответ

0 голосов
/ 23 июня 2018

Так что в основном он работает по принципу бинарного поиска, как вы указали.

Вот алгоритм разбит простым языком

  • Сначала вы обнаружите первое вхождение искомой цели
    • Если цель не обнаружена, вернуть [-1, -1]

  • Затем найдите первое вхождение target+1, предположим, что это вхождение сохранено в переменной end, тогда последнее вхождение исходного target будет `end -1

    Сначала вы обнаружите первое вхождение цели, которую вы ищете
    Пример массива nums = [5,7,7,8,8,10], target = 8

  • lo = 0, hi = len(nums), mid = (hi+lo)//2

  • Теперь вы ищите середину массива, здесь mid = 3
  • Элемент в nums [3] равен 8, что совпадает с taget
  • Это начальный индекс, верните его и сохраните в значении start

Теперь, когда мы получили первый случай, мы переходим к следующему этапу

Тогда найдите первое вхождение target+1

  1. lo = 0, hi = len(nums), mid = (hi+lo)//2, target+1 = 9
  2. Теперь вы ищите середину массива, здесь mid = 3
  3. Элемент с номерами [3] равен 8, что меньше target+1, поэтому мы устанавливаем low = mid +1
  4. Далее мы устанавливаем mid = (hi+lo)//2, что составляет 5
  5. Элемент с номерами [5] равен 10, что больше target+1, поэтому мы устанавливаем hi = mid
  6. После предыдущего шага мы выходим из while loop, так как условие while lo<hi оценивается как False
  7. REturn lo в качестве конечного индекса

Теперь у нас есть start = 3 и end = 5, поэтому мы возвращаем [start, end-1], т.е. [3,4]

Справка:

...