假設我有一個整數陣列：
[ 1,2,3,4,5,6,1,2,3,1,2... ]
我想知道 K 最常見的元素。短語“ K最頻繁”立即讓我想到了最大堆資料結構，因此我決定創建一個自定義物件來計算元素的數量和優先級：
public class countedInts implements Comparable<countedInts>{
public int theInt, count;
public countedInts(int a, int b) {
this.theInt = a;
this.count = b;
}
@Override
public int compareTo(countedInts o) {
return this.count - o.count;
}
}
這個物件本質上是兩個整數，配對在一起。簡單的。
好的：現在主要代碼：
public int[] topKFreq(int[] arr, int k) {
PriorityQueue<countedInts> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for( int i=0; i<arr.length; i ) {
// If arr[i] is not tracked with a countedInts object:
maxHeap.offer( new countedInts(arr[i], 1) );
// But if arr[i] is already stored within a countedInts object...
countedInts tmp = maxHeap.get( ??? );
tmp.count ;
maxHeap.offer( tmp );
}
}
你看到了問題。當我考慮 中的元素時arr，我需要一種方法來檢查maxHeap我是否有一個countedInts物件已經在檢查該元素。我需要查看PriorityQueue中物件的成員。有沒有辦法做到這一點？或者有沒有更好的策略來解決這個問題。
完全披露：是的，這是一個 LeetCode 問題。我總是喜歡在放棄之前研究解決方案并查看解決方案。這是一種更好的學習方式。
==================================================== ======================
[編輯] :: 一位用戶建議了以下策略，該策略有效。發布以防萬一它可以幫助別人......
public class countedInts implements Comparable<countedInts>{
public int theInt, count;
public countedInts(int a, int b) {
this.theInt = a;
this.count = b;
}
@Override
public int compareTo(countedInts o) {
return this.count - o.count;
}
}
public int[] topKFrequent(int[] arr, int k) {
// Edge cases
if( arr == null ) {
return null;
}
else if( arr.length == 0 ) {
return arr;
}
int[] ret = new int[k];
HashMap<Integer,Integer> myMap = new HashMap<>();
PriorityQueue<countedInts> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// Populate HashMap
for( int i=0; i<arr.length; i ) {
if( !myMap.containsKey(arr[i]) ) {
myMap.put(arr[i], 1);
}
else {
myMap.put(arr[i], myMap.get(arr[i]) 1);
}
}
// Transfer data into MaxHeap
for( Map.Entry<Integer, Integer> glork : myMap.entrySet() ) {
maxHeap.offer( new countedInts(glork.getKey(), glork.getValue()) );
}
// Pick out K-most values
for( int i=0; i<k; i ) {
countedInts tmp = maxHeap.poll();
ret[i] = tmp.theInt;
}
return ret;
}
uj5u.com熱心網友回復：
一種使用流的方法，我認為它以某種方式自我記錄：
在您的陣列上流式傳輸，按身份分組并使用映射到頻率Collectors.counting，在結果映射上流式傳輸，按值以相反的順序對條目進行排序，將流限制為k元素，并映射到鍵
public int[] topKFrequent(int[] nums, int k) {
return Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
.entrySet().stream()
.sorted(Map.Entry.<Integer, Long>comparingByValue().reversed())
.limit(k)
.map(Map.Entry::getKey)
.mapToInt(Integer::intValue)
.toArray();
}
uj5u.com熱心網友回復：
您可以首先使用 HashMap 來計算給定陣列中所有數字的頻率。
然后遍歷 hashmap 以創建CountedInts物件并將這些物件插入優先級佇列。
uj5u.com熱心網友回復：
正如@Haoliang的回答中所述，您可以生成一個Map包含源陣列中每個數字的頻率的。PriorityQueue然后使用此地圖的條目填充 a 。
這種方法比對所有條目進行排序更有效，尤其是當k它遠低于陣列中的數字元素時。
這就是代碼的樣子：
public static int[] topKFrequent(int[] nums, int k) {
int[] result = new int[k];
Map<Integer, Integer> freq = getFrequencies(nums);
Queue<Map.Entry<Integer, Integer>> entries = populateQueue(freq);
for (int i = 0; i < result.length; i ) {
result[i] = entries.remove().getKey();
}
return result;
}
Java 8 方法merge()用于使生成地圖頻率的代碼更簡潔：
public static Map<Integer, Integer> getFrequencies(int[] arr) {
Map<Integer, Integer> hist = new HashMap<>();
for (int next: arr) {
hist.merge(next, 1, Integer::sum);
}
return hist;
}
下面提供的方法使用map的條目創建一個Max HeapPriorityQueue并填充它：
public static Queue<Map.Entry<Integer, Integer>> populateQueue(Map<Integer, Integer> hist) {
Queue<Map.Entry<Integer, Integer>> entries =
new PriorityQueue<>(Map.Entry.<Integer, Integer>comparingByValue().reversed());
entries.addAll(hist.entrySet());
return entries;
}
main()
public static void main(String[] args) {
int[] nums = {1, 1, 1, 2, 2, 3};
System.out.println(Arrays.toString(topKFrequent(nums, 2)));
nums = new int[]{1};
System.out.println(Arrays.toString(topKFrequent(nums, 1)));
}
輸出：
[1, 2]
[1]
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/490357.html