สมมติว่าเรามีอาร์เรย์จำนวนเต็มที่ไม่ว่างเปล่า เราต้องส่งคืนองค์ประกอบที่ kth บ่อยที่สุด ดังนั้นหากองค์ประกอบคือ [1,1,1,1,2,2,3,3,3] และ k =2 ผลลัพธ์จะเป็น
อย่างเป็นทางการ ฟังก์ชันควร −
- คืนค่า จริง ถ้ามี i, j, k
- เช่นนั้น arr[i]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- num_freq =แผนที่ว่าง freq_list :=แผนที่ว่าง
- สำหรับแต่ละองค์ประกอบ i เป็น nums
- ถ้าฉันไม่ได้อยู่ใน num_freq ดังนั้น num_freq[i] :=1 มิฉะนั้น ให้เพิ่ม num_freq[i] ขึ้น 1
- สำหรับคู่คีย์-ค่าแต่ละคู่ในแผนที่ num_freq
- หากไม่มีค่าใน freq_list ดังนั้น freq_list[value] :=รายการที่มี [คีย์] หรือแทรกคีย์ลงในอาร์เรย์ freq_list[value]
- res :=รายการว่าง
- สำหรับ i :=ความยาวของตัวเลขลงไปที่ 0
- ถ้าฉันอยู่ใน freq_list ให้เพิ่มองค์ประกอบของ freq_list[i] ลงใน res
- ถ้าความยาวของ res>=k ให้แตก
- ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object):
def topKFrequent(self, nums, k):
number_frequency = {}
frequency_list ={}
for i in nums:
if i not in number_frequency:
number_frequency[i] = 1
else:
number_frequency[i] += 1
for key,value in number_frequency.items():
if value not in frequency_list:
frequency_list[value] = [key]
else:
frequency_list[value].append(key)
result = []
for i in range(len(nums),0,-1):
if i in frequency_list:
result.extend(frequency_list[i])
if len(result) >=k:
break
return result
ob1 = Solution()
print(ob1.topKFrequent([1,1,1,1,2,2,3,3,3], 2)) อินพุต
[1,1,1,1,2,2,3,3,3] 2
ผลลัพธ์
[1, 3]
