Median Maintainence - 중간 값 찾기 문제
6179 단어 media
무 작위 로 한 줄 의 수 i 를 드 립 니 다. 그 중 크기 와 중간 에 있 는 그 수 를 드 립 니 다.
알고리즘 설명:
일반적인 방법 은 삽입 정렬 을 한 다음 에 중간 값 은 색인 의 절반 위치 에 있 고 시간 복잡 도 는 보통 이 며 정렬 평균 시간 복잡 도 O (n2) 를 삽입 한 다음 에 중간 을 찾 습 니 다.
값, 효율 이 높 지 않다.
여기 서 는 데이터 구조 인 Heap 를 도입 해 문 제 를 해결 하 는 방식 으로, 시간 복잡 도 는 O (logn) 다.
두 개의 더 미 를 도입 하고 max heap 와 min heap 를 통 해 전체 문자열 i 의 두 부분 을 저장 하려 면 다음 과 같은 조건 을 만족 시 켜 야 합 니 다.
1. 크기 조건
max heap 의 요소 개 수 는 min 의 것 보다 1 개 많 거나 같 을 수 있 습 니 다. 그렇지 않 으 면 조정 할 수 있 습 니 다.
2. 순서 조건
max heap 에 앞부분 작은 값 저장
min 힙 에 후반 부 큰 값 저장
max heap 에서 가장 큰 값 은 min 에서 가장 작은 값 보다 작 거나 같 을 수 있 습 니 다. 그렇지 않 으 면 조정 할 수 있 습 니 다.
즉, median 은 max heap 의 지붕 이나 max heap 의 지붕 과 min heap 의 지붕 의 평균 값 을 생 성 합 니 다.
코드 는 다음 과 같 습 니 다:
class MyHeap:
# heap type
MAX_HEAP = 1
MIN_HEAP = 0
def __init__(self, type=MAX_HEAP, arr=None):
self.type = type
# if init directly by array
if arr is not None:
self.data = arr[:]
length = len(arr)
# the last non leave node
begin = length / 2 - 1
for i in range(begin, -1, -1):
self.heapify(i)
else:
self.data = []
def __heapify(self, i):
length = len(self.data)
left = self.__leftChild(i)
right = self.__rightChild(i)
largest = i
while left < length or right < length:
if self.type == self.MAX_HEAP:
if left < length and self.data[left] > self.data[largest]:
largest = left
if right < length and self.data[right] > self.data[largest]:
largest = right
elif self.type == self.MIN_HEAP:
if left < length and self.data[left] < self.data[largest]:
largest = left
if right < length and self.data[right] < self.data[largest]:
largest = right
if i != largest:
self.__swap(i, largest)
i = largest
left = self.__leftChild(i)
right = self.__rightChild(i)
else:
break
def inset(self, item):
self.data.insert(0, item)
# heapify starts from 0
self.__heapify(0)
def delete(self, index):
self.data.pop(index)
# if delete the 0 index item, heapify from 0
self.heapify(index - 1 if index - 1 else 0)
def pop(self):
# pop the extreme value, what ever it is max or min
self.__swap(0, len(self.data) - 1)
extreme = self.data.pop()
self.__heapify(0)
return extreme
# overwrite the getitem method of MyHeap class,
# so you can use [] to get value by index
def __getitem__(self, index):
if len(self.data) == 0:
raise Error("no items")
return self.data[index]
# overwrite the len method of MyHeap class,
# so you can len(heapclass) to get the size of heap
def __len__(self):
return len(self.data)
def __swap(self, i, j):
temp = self.data[i]
self.data[i] = self.data[j]
self.data[j] = temp
# index of array starts from zero
def __rightChild(self, i):
return 2 * i + 1
def __leftChild(self, i):
return 2 * i + 2
# overwrite the repr method of MyHeap class,
# so you can print the readability info of heap
def __repr__(self):
return str(self.data)
class MedianMaintain:
def __init__(self):
self.maxHeap = MyHeap(MyHeap.MAX_HEAP)
self.minHeap = MyHeap(MyHeap.MIN_HEAP)
# the total number of items in both heaps
self.N = 0
def insert(self, item):
# to obey size requirement rule, before insertion, if
# total number is even, it is OK, insert new item to
# max heap, and then adjust it
if self.N % 2 == 0:
self.maxHeap.inset(item)
self.N += 1
if len(self.minHeap) == 0:
return
# to obey order requirement rule, largest of items in max heap should
# less or equal than smallest of the items in the min heap, if not,
# swap them
if self.maxHeap[0] > self.minHeap[0]:
toMin = self.maxHeap.pop()
toMax = self.minHeap.pop()
self.maxHeap.inset(toMax)
self.minHeap.inset(toMin)
else:
# to obey the size requirement rule, before insertion, if the size of
# max heap is odd, then to insert the new item, and pop the extreme value
# to insert into min heap
self.maxHeap.inset(item)
toMin = self.maxHeap.pop()
self.minHeap.inset(toMin)
self.N += 1
def getMedian(self):
# if total size if even, the median is the average of value of root of min and max heap
if self.N % 2 == 0:
return (self.maxHeap[0] + self.minHeap[0]) / 2.0
else:
# if total size if odd, median is root of max heap
return self.maxHeap[0]
def __repr__(self):
return "max heap: " + str(self.maxHeap) + '
' + "min heap: " + str(self.minHeap)
if __name__ == "__main__":
medianMaintain = MedianMaintain()
medianMaintain.insert(5)
medianMaintain.insert(4)
medianMaintain.insert(3)
medianMaintain.insert(2)
medianMaintain.insert(1)
medianMaintain.insert(6)
print medianMaintain
print medianMaintain.getMedian()
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Media Query를 사용하여 데스크톱, 태블릿 및 모바일을 타겟팅하는 방법은 무엇입니까?미디어 쿼리는 화면 크기와 해상도가 다른 다양한 장치에 스타일 시트를 제공하는 데 널리 사용되는 방법입니다. 여러 장치에서 웹 사이트의 모양을 변경하는 데 사용됩니다. 미디어 쿼리는 미디어 유형과 참 또는 거짓이 될...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
