Почему сложность времени отличается, даже когда я использую только один цикл? - PullRequest
Новая
       16

Почему сложность времени отличается, даже когда я использую только один цикл?

0 голосов
/ 29 декабря 2018

Я решаю вопрос о CodeLab, который просит удалить дубликаты на месте так, чтобы каждый элемент мог появляться не более двух раз и возвращать новую длину.

При заданном входном массиве A = [1,1,1, 2] Ваша функция должна возвращать length = 3, и A теперь [1,1,2]

Мой код Python работает нормально, и он корректен, но говорит, что время выполнения (сложность по времени) слишком великодолго.Но когда я запускаю похожий Java-код (один цикл), он принимает его.Что я делаю неправильно в коде Python, так что время слишком много? 

def removeDuplicates(A):
    if len(A) <= 2:
        return len(A)
    i = 0
    n = len(A)
    while i < n:
        if i <= len(A)-3:
            if A[i] == A[i+1] and A[i] == A[i+2]:
                del A[i]
                i -= 1
        i += 1
    return i

Код Java: 

public int removeDuplicates(ArrayList<Integer> a) {
    int count = 1;
    int shiftLeft = 0;
    int i = 1;
    while (i < a.size()){
        a.set(i-shiftLeft, a.get(i));
        if (a.get(i-1-shiftLeft).equals(a.get(i))){
            count ++;
        }
        else {
            count = 1;
        }
        if (count == 3){
            shiftLeft ++;
            count --;
        }
        i ++;
    }
    for (int j=0; j<shiftLeft; j++){
        a.remove(a.size()-1);
    }
    return a.size();
}

1 Ответ

0 голосов
/ 29 декабря 2018

Удаление из массива по заданному индексу занимает линейное время.Это потому, что вы должны сдвинуть все элементы справа от него на один пробел влево, что также занимает O (n).

Вы можете выполнить удаление в постоянное время, используя следующий трюк.Сначала поменяйте местами элемент, который вы хотите удалить, в конец массива, а затем уменьшите размер массива на один элемент, используя pop().

. Вы не можете реализовать такое удаление общего назначения, потому что хотямассив не отсортирован, у него все еще может быть какой-то определенный порядок, который необходимо сохранить.

Возвращаясь к проблеме: вы получили ограничение, что вы должны реализовать его на месте,без дополнительного пространства, и только один цикл.Тем не менее, это лучшее, что я могу придумать сейчас: 

l = [1, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6]

def removeDuplicates(l):
    for i in range(len(l) - 1, 0, -1): 
        if (l[:i]).count(l[i]) >= 2:
            del l[i]
    return(l)

print(removeDuplicates(A)) #=> 8
print(l) #=> [1, 2, 3, 4, 4, 5, 5, 6]
...