Jz28__数组中出现次数超过一半的数字

CPU-Code · CPU-Code · commit f2ddb275c1d2 · 2021-01-21T12:07:07.000+08:00
diff --git a/Offer/src/com/cpucode/java/getting/started/Jz28.java b/Offer/src/com/cpucode/java/getting/started/Jz28.java
@@ -1,5 +1,9 @@
 package com.cpucode.java.getting.started;
 
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Arrays;
+
 /**
  * 题目描述
  * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
@@ -17,4 +21,102 @@
  * @CSDN : https://blog.csdn.net/qq_44226094
  */
 public class Jz28 {
+    public int MoreThanHalfNum_Solution(int [] array) {
+        Map<Integer, Integer> map = new HashMap<>(array.length + 1);
+
+        for(int i = 0; i < array.length; i++){
+            /**
+             * 查询是否有这个key
+             * */
+            if(map.containsKey(array[i])){
+                /**
+                 * 有出现就加一
+                 * */
+                map.put(array[i], map.get(array[i]) + 1);
+            } else{
+                /**
+                 * 第一次出现这个key
+                 * */
+                map.put(array[i], 1);
+            }
+
+            /**
+             * 查询是否大于数组一半
+             * */
+            if(map.get(array[i]) > (array.length/2)){
+                return array[i];
+            }
+        }
+
+        return 0;
+    }
+
+    public int MoreThanHalfNum_Solution1(int [] array) {
+        /**
+         * 排序
+         * */
+        Arrays.sort(array);
+
+        int count = 0;
+        /**
+         * 中间下标, 如果众数大于一半, 就绝对在中间
+         * */
+        int half = array.length/2;
+
+        for(int num : array){
+            if(num == array[half]){
+                /**
+                 * 记录中间值的数量
+                 * */
+                count++;
+            }
+        }
+
+        if(count > half){
+            return array[half];
+        }else{
+            return 0;
+        }
+    }
+
+    public int MoreThanHalfNum_Solution2(int [] array) {
+        int cond = -1;
+        int cnt = 0;
+
+        for(int num : array){
+
+            if(cnt == 0){
+                /**
+                 * 找到新的众数
+                 * */
+                cond = num;
+                cnt++;
+            }else{
+                if(cond == num){
+                    /**
+                     * 和众数一样
+                     * */
+                    cnt++;
+                }else{
+                    /**
+                     * 和众数不一样
+                     * */
+                    cnt--;
+                }
+            }
+        }
+
+        cnt = 0;
+
+        for(int num : array){
+            if(num == cond){
+                cnt++;
+            }
+            if(cnt > array.length/2){
+                return cond;
+            }
+        }
+
+        return 0;
+    }
 }
diff --git a/README.md b/README.md
@@ -815,7 +815,7 @@ java编程基础 面向对象 javaAPI 集合 IO GUI JD8C 多线程 网络编程
 - [x] [Jz9__变态跳台阶](Offer/src/com/cpucode/java/getting/started/Jz9.java)
 - [x] [Jz16__合并两个排序的链表](Offer/src/com/cpucode/java/getting/started/Jz16.java)
 - [x] [Jz18__二叉树的镜像](Offer/src/com/cpucode/java/getting/started/Jz18.java)
-- [ ] [Jz28__数组中出现次数超过一半的数字](Offer/src/com/cpucode/java/getting/started/Jz28.java)
+- [x] [Jz28__数组中出现次数超过一半的数字](Offer/src/com/cpucode/java/getting/started/Jz28.java)
 
 
 - [返回目录](#文件目录)
