AoC 퍼즐 작업을 할 때 목록을 빼고 싶었습니다 (순서 유지).
def bag_sub(list_big, sublist):
result = list_big[:]
for n in sublist:
result.remove(n)
return result
필자는 list.remove불필요하게 비효율적으로 보이는 호출 (그 자체가 O (n))이 루프 내에 포함되는 방식이 마음에 들지 않았습니다 . 그래서 그것을 피하기 위해 다시 작성하려고했습니다.
def bag_sub(list_big, sublist):
c = Counter(sublist)
result = []
for k in list_big:
if k in c:
c -= Counter({k: 1})
else:
result.append(k)
return result
이것은 지금 O (n) Counter.__isub__입니까 , 아니면 사용법이 여전히 문제가 있습니까?
이 접근 방식은 요소가 해시 가능해야하며 원본에는 없었던 제한 사항입니다. 이 추가 제한을 생성하지 않는 O (n) 솔루션이 있습니까? 파이썬보다 더 나은 "가방"데이터 유형이 collections.Counter있습니까?
sublist길이의 절반 이라고 가정 할 수 있습니다 list_big.
이것은 지금 O (n)
Counter.__isub__입니까 , 아니면 사용법이 여전히 문제가 있습니까?
이것은 Counter.__isub__양수가 아닌 값을 버릴 때 모든 키 를 통과 한다는 점을 제외하면 예상되는 경우 O (n) 입니다. 키 값에서 "일반적인"방식으로 1을 빼고 c[k]대신 확인하는 것이 좋습니다 k in c. (의 c[k]경우 0 k not in c이므로 in확인이 필요하지 않습니다 .)
if c[k]:
c[k] -= 1
else:
result.append(k)
이 추가 제한을 생성하지 않는 O (n) 솔루션이 있습니까?
입력이 정렬 된 경우에만 병합 정렬 병합의 표준 변형이이를 수행 할 수 있습니다.
파이썬보다 더 나은 "가방"데이터 유형이
collections.Counter있습니까?
collections.Counter 파이썬의 가방입니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다