算法筆試模拟題精解之“最活躍的數”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第45題：最活躍的數 的題目解析，具體如下：

題目描述

題目等級：簡單

知識點：數組

檢視題目：最活躍的數

現有一個包含n個整數的序列(1<=n<=1e5)，n個數分别是a1,a2,a3...an(0<=ai<=1e5)，現在對于每個ai都有3種操作，一種是使ai+1，一種是使ai-1，還有一種是不變，問在對這n個數操作完後，出現次數最多的數的出現次數是多少。

輸入序列中整數個數n，和n個整數[a1,a2,…,an]

輸出一個數，表示在操作過後的出現次數最多的數的出現次數

示例1

輸入：

8

[3,2,1,5,3,4,9,5]

輸出：

5

解題方法

根據題意，每個數都有3種操作，一種是+1，一種是-1，還有一種是不變。操作過後出現次數最多的數設為n，則操作之前 n，n+1, n-1 三個數的出現次數應為最多。

是以可以這樣做，将數組中每個數的出現次數通過 HashMap 進行統計，以數組中的數字作為 key，每個數字出現的次數作為 value。将數組中的數字存入 HashMap 中後，周遊 HashMap ，對于每一個 key ，統計key-1，key，key+1 的 value 之和，周遊完 HashMap 後，得到的最大 value 和就是答案。

時間複雜度：O(n)

空間複雜度：O(n)

看完之後是不是有了想法了呢，快來練練手吧>>