[A] 添加TOPK思路；[A] 华为机试题

coderbruis · coderbruis · commit 977e186cc0d2 · 2020-08-27T22:07:28.000+08:00
diff --git a/src/main/java/com/bruis/algorithminjava/algorithm/huawei/Question01.java b/src/main/java/com/bruis/algorithminjava/algorithm/huawei/Question01.java
@@ -0,0 +1,54 @@
+package com.bruis.algorithminjava.algorithm.huawei;
+
+import java.util.Scanner;
+
+/**
+ * @author LuoHaiYang
+ *
+ * 题目描述：输入一个int型的正整数，计算出该int型数据在内存中存储时1的个数。
+ *
+ * 输入描述： 输入一个整数（int类型）
+ *
+ * 输出描述： 这个数转换成2进制后，输出1的个数
+ *
+ * 实例1：
+ *
+ * 输入：5
+ * 输出：2
+ *
+ */
+public class Question01 {
+
+    /**
+     * 笨办法
+     * @param args
+     */
+    public static void main(String[] args) {
+
+        // 巧妙法，通过二进制位运算
+        Scanner in = new Scanner(System.in);
+
+        int count = in.nextInt(), result = 0;
+        while (count > 0) {
+            if ((count & 1) > 0) {
+                result++;
+            }
+            count = count >> 1;
+        }
+        System.out.println(result);
+/*
+        笨办法
+        Scanner scanner = new Scanner(System.in);
+        int input = scanner.nextInt();
+        char[] bytes = Integer.toBinaryString(input).toCharArray();
+        int result = 0;
+        for (char c : bytes) {
+            if (c == '1') {
+                result++;
+            }
+        }
+        System.out.println(result);
+*/
+    }
+
+}
diff --git a/src/main/java/com/bruis/algorithminjava/algorithm/leetcode/array/TopKFrequentElements.java b/src/main/java/com/bruis/algorithminjava/algorithm/leetcode/array/TopKFrequentElements.java
@@ -14,10 +14,12 @@ public class TopKFrequentElements {
 
     /**
      *
-     *
+     * 桶排序
      *
      */
     public int[] topKFrequent(int[] nums, int k) {
+        List<Integer> res = new ArrayList<>();
+
         if (nums == null || nums.length < 2) {
             return nums;
         }
@@ -32,23 +34,29 @@ public int[] topKFrequent(int[] nums, int k) {
             }
         }
 
-        List<Integer> result = new ArrayList<>();
-
-        Set<Map.Entry<Integer, Integer>> entries = count.entrySet();
-
-        for (Map.Entry<Integer, Integer> entry : entries) {
-            if (entry.getValue() > k) {
-                result.add(entry.getKey());
+        List<Integer>[] list = new List[nums.length];
+        for (int key : count.keySet()) {
+            // 让频率作为下标
+            int i = count.get(key);
+            if (list[i] == null) {
+                list[i] = new ArrayList<>();
             }
+            // key表示的是元素
+            list[i].add(key);
         }
 
+        for (int i = list.length - 1; i >= 0 && res.size() < k; i--) {
+            if (list[i] == null) {
+                continue;
+            }
+            res.addAll(list[i]);
 
-        int[] res = new int[result.size()];
-
-        for (int i = 0; i < result.size(); i++) {
-            res[i] = result.get(i);
         }
-        return res.length > 0 ? res : nums;
+        int[] result = new int[res.size()];
+        for (int i = 0; i < res.size(); i++) {
+            result[i] = res.get(i);
+        }
+        return result;
     }
 
     public static void main(String[] args) {
