Почему алгоритм разделения четных и нечетных чисел в массиве не работает для разделения вокруг оси? - PullRequest
Новая
       22

Почему алгоритм разделения четных и нечетных чисел в массиве не работает для разделения вокруг оси?

0 голосов
/ 16 марта 2020

Мы используем следующий алгоритм, чтобы вывести все четные слева и все нечетные справа от массива: 

    def evenOddPartition(self,nums):
    # partition an array such that all even are on the left
    # and all odd are on the right

    i = 0
    j = len(nums) - 1

    while i < j:
        ## if i is even skip this index
        if nums[i]%2 == 0:
            i+=1
        elif nums[j] %2 == 0:
            ## if nums[i] is odd and nums[j] is even
            nums[i],nums[j] = nums[j],nums[i]
            j-= 1
        else:
            ## both are odd 
            ## decrement j (i.e try to see if there is any other even before it)
            j-=1

    return nums

Even / Odd - это двоичная классификация типа true false.

Теперь у меня вопрос, почему мы не можем применить эту же двоичную классификацию к таким проблемам:

Рассмотрим этот массив: y = [2,3,5, -100,100,5, 5,6,3,5]

И вас просят переместить все элементы <= 5 в левую сторону и все> 5 в правую сторону:

Используя те же логики c в качестве четной / нечетной задачи я представляю этот код 

    def tryTwo(self,nums):
    pivot = 5

    i = 0
    j = len(nums) - 1

    while i < j:
        if nums[i] < pivot:
            i+=1
        elif nums[i] == pivot:
            i+=1
        elif nums[i] > pivot:
            if nums[j] <= pivot:
                nums[i], nums[j] = nums[j], nums[i]
                j-=1

            else:
                j-=1
        else:
            j-=1

    return nums

Однако этот код выводит [2, 3, 5, -100, 5, 5, 5, 3, 6, 100], что неправильный ответ Правильный ответ примерно такой:

[2, 3, -100, 3, 5, 5, 5, 5, 100, 6]

Чего мне здесь не хватает? Есть ли ошибка в моем втором коде?

1 Ответ

0 голосов
/ 17 марта 2020

Привет :) Вы заявили, что вам дано задание

Вас просят переместить все элементы <= 5 в левую сторону и все> 5 в правую сторону

Это означает, что вывод [2, 3, 5, -100, 5, 5, 5, 3, 6, 100] является абсолютно действительным.

Все элементы, которые меньше ИЛИ , равное 5, перемещаются в левую часть списка

[2, 3, 5, -100, 5, 5, 5, 3,.

А остальные смещены вправо

6, 100].

Как упомянул Blastfurnace, ваш код рассматривает каждое число ниже 6 как одно и то же и не имеет никакого механизма сортировки для этих чисел. Поэтому имеет смысл, чтобы 3 было после 5 (так как эти числа не отсортированы).

Если вы хотите, чтобы все элементы были меньше 5 слева, каждые 5 с в середине и все больше, чем 5 справа вам понадобится другой алгоритм (или просто используйте алгоритм сортировки).

...