LeetCode 347. 앞의 K 고주파 원소
6924 단어 LeetCode데이터 구조 와 알고리즘
빈 정수 그룹 을 지정 하고 주파수 가 나 오기 전에 k 가 높 은 요 소 를 되 돌려 줍 니 다.
예시 1:
: nums = [1,1,1,2,2,3], k = 2
: [1,2]
예시 2:
: nums = [1], k = 1
: [1]
설명:
4. 567917. 주어진 k 가 항상 합 리 적 이 고 1 ≤ k ≤ 배열 에서 서로 다른 요소 의 개 수 를 가정 할 수 있 습 니 다
4. 567917. 당신 의 알고리즘 은 시간 복잡 도가 O (n log n) 보다 높 아야 합 니 다. n 은 배열 의 크기 입 니 다
해제
제 코드 사 고 는 주로 사전 기록 어 - 주파수 쌍 을 사용 한 다음 에 체인 법 으로 하 쉬 표 로 역방향 으로 저장 하 는 동시에 빈 도 를 하나의 list 로 저장 하고 높 은 것 에서 낮은 순서 로 각각 반대 방향 으로 가 는 하 쉬 표 에서 찾 습 니 다. 같은 주파수 의 것 은 한 번 만 찾 고 마지막 에 출력 하 며 시간 복잡 도 는 nlogn 이 어야 합 니 다. 주로 정렬 복잡 도 입 니 다.코드 는 다음 과 같 습 니 다:
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
result = []
values = []
reversehashtable = {}
hashtable = {}
for i in range(len(nums)):
hashtable[nums[i]] = hashtable.get(nums[i],0) + 1
for key in hashtable:
reversehashtable[hashtable[key]] = reversehashtable.get(hashtable[key],[])
reversehashtable[hashtable[key]].append(key)
values.append(hashtable[key])
print(values)
values.sort(reverse = True)
#print(hashtable, reversehashtable)
for i in range(k):
if i == 0:
result.extend(reversehashtable[values[i]])
if values[i] != values[i-1] and i > 0 :
result.extend(reversehashtable[values[i]])
if values[i] == values[i-1] and i > 0:
continue
return result
토론 구역
하나의 생각 은 해시 표를 만 든 후에 더미 로 앞의 k 개 를 실현 하 는 것 이기 때문에 쌓 인 복잡 도 는 nlogn 이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
