每天一道劍指offer-數組中出現次數超過一半的數字

• 2019 年 10 月 4 日
• 筆記

前言

今天的題目 每天的題目見github(看最新的日期): https://github.com/gzc426 具體的題目可以去牛客網對應專題去找。

昨天的題解

題目

每天一道劍指offer-數組中出現次數超過一半的數字 來源： https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

題目詳述

數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由於數字2在數組中出現了5次，超過數組長度的一半，因此輸出2。如果不存在則輸出0。

題目詳解

思路

• 使用一個計數count = 1，當前數num,每當數組中數和當前數num相同，那麼count就加1，不相同就減一，因為是找出現的數超過數組的長度的一半，所以最後如果有出現的數超過數組長度一半的，count肯定是大於0的數

程式碼

public class Solution {      public int MoreThanHalfNum_Solution(int [] array) {          if(array.length == 0)              return 0;          int count = 1;          int number = array[0];          for(int i=1;i<array.length;i++)          {              if(array[i] == number)              {//如果與number相等，那麼count++，可能是超過一半的那個數                  count++;              }else{                  count--;//如果與number不相等，count就減一                  if(count == 0)                  {//如果count等於0了，說明這個數在這裡出現次數已經被抵消了                      count = 1;//重新記錄count為1                      number = array[i];//number記錄當前這個數                  }              }          }          if(count > 0)          {//如果count大於0說明有可能存在這樣的數，是出現次數大於數組的一半的           //還有一種可能是最後剛好一個數連續出現了2次，導致count>0              count = 0;              for(int i=0;i<array.length;i++)              {//去遍曆數組，計數這個number到底出現了幾次                  if(number == array[i])                      count++;              }              if(count > array.length/2)                  return number;//出現超過一半          }          return 0;      }  }

程式碼截圖（避免亂碼）