Найти kthsmallestnumber с помощью бинарного поиска - Массив только для чтения - PullRequest
Новая
       16

Найти kthsmallestnumber с помощью бинарного поиска - Массив только для чтения

0 голосов
/ 18 мая 2019

Проблема: «Найти k-е наименьшее число в массиве только для чтения без изменения исходного массива»

Одно из решений, опубликованных на форуме ниже, не выполняется при тестировании с несколькими дубликатами.Какие-либо предложения ? Как найти K-е наименьшее целое число в несортированном массиве только для чтения?

Подход с использованием бинарного поиска не работает для следующих тестовых случаев, в которых есть ошибки: 



def kthsmallestUsingBinarySearch(a, k):

    if(a == None or len(a) == 0):
         print("Not valid array")
    lo =  min(a);
    hi = max(a);

   while(lo <= hi):

        mid = int(lo + (hi - lo)/2);

       print("low: {0} and high : {1} and mid:{2}".format(lo,hi,mid))
       countLess = countEqual = 0

       for i in range(0,len(a)):
           print("{0} <= {1}".format(a[i],mid)) 
           if(a[i] < mid):
              countLess +=1
           elif(a[i] == mid):
              countEqual +=1

           if(countLess >= k):
              break


       if(countLess < k and countLess + countEqual >= k):
            print("The mid element is :{}".format(mid))
            return mid
       elif(countLess >= k):
            hi = mid - 1
       else:
           lo = mid + 1

     return -1

Работает, как и ожидалось, для положительных чисел без дублирования.

<---- Правильные результаты для ввода без дублирования: ---->

1.1 Используя бинарный поиск, 2 наименьших элемента в [10, 1, 5, 3, 0, 6, 11]: 1

1.2 При использовании бинарного поиска 3 наименьших элемента в [10, 2, 5, 3, 0, 6, 11] составляют: 3

<------ Неудачные тестовые случаи: ---->

2.1 При использовании бинарного поиска 2 наименьших элемента в [10, 4, 4] составляют: 4

2.2 При использовании бинарного поиска 4 наименьших элемента в [10, 4, 4, 2, 2, 2, 1] составляют: 2

2.3 При использовании бинарного поиска 4 наименьших элемента в [3, 2, 3,1, 2, 4, 5, 5, 6] составляет: 3

...