筆試面試題目：阿里選班長

週末了，抽點時間練習算法，順便保持對代碼的感覺，免得生疏。畢竟，拳不離手，曲不離口。

今天，我們來看阿里巴巴公司的一道面試算法題目，初看起來挺簡單的，其實不然。題目如下：

已知數組中有一個數字出現的次數，超過數組長度的一半，要求找出這個數字。

有的人看到題目後就開始做，也能得到正確結果，但無法通過面試，這是爲什麼呢？且往下看。

一. 暴力排序

排序是最容易想到的一種方法。由於目標元素的次數超過數組長度的一半，所以排序後直接取中間元素就行。

阿里巴巴會出這麼簡單的題目嗎？有點搞笑！我們知道，基於比較的排序，時間複雜度能達到 O(NlogN), 但這不是最好的方法，無法通過面試。

二. 計數統計

既然題目的意思是求出這個次數超過一半的元素，那就對次數進行計數吧，直接搞個 hashmap 就行了。此時，時間複雜度是 O(N), 但空間複雜度也是 O(N)，無法通過面試。

而且要注意到，使用計數法的時候，漏用了題目中的信息：超過數組長度的一半。顯然，這是不合理的。這就跟你高考數學一樣，你發現有個條件居然沒用到，而你把題目做出來了，那是很值得懷疑的。

三. 摩爾投票

接下來，我們來介紹一種很巧妙的思路，即摩爾投票法，時間複雜度是 O(N), 空間複雜度是 O(1)，能滿足面試要求。思路是怎樣的呢？

我們來看一種現實中的投票場景：

班級要開始選班長

要求半數以上通過

選出來的就是班長

我們先來看一種簡單的情況：假如只有 2 個人 A 和 B 競爭班長這一職位。那麼，在大家投票後，我們從投票箱中取數後，可以這樣統計：

如此循環，直到所有票統計完畢，最後有票的一方，就是勝利者，就是大家選出來的班長。

如上只是兩方進行 PK, 那麼，當候選人爲多人時，也可以使用類似的思路，這裏的前提條件就是：一定存在多餘半數票的候選人。

當多方進行 PK 時，佔據着半數以上票數的班長，可以任性地抵消任何人的票，而且其他人之間的相互抵消也不會撼動班長的位置。

有的朋友看到這裏，可能覺得有點繞，那麼，我們一起來看看程序，並打印關鍵步驟，有興趣的朋友可以對照程序和結果理解下。

阿里巴巴主要是用 Java 編程, 但也有 C++ 崗位，如下是對應的 C++ 程序代碼：

#include <iostream>
using namespace std;
int solution(int a[], int n) {    
  int count = 0, value = a[0];
  for(int i = 0; i < n; i++)
  {
    printf("log, i=%d, count=%d, value=%d\n", i, count, value);
    if(count == 0)
    {
      value = a[i];
    }
    if(a[i] == value)
    {
      count++;
    }
    else
    {
      count--;
    } 
  }
  return value;
}
int main()
{
   int a[]={6,2,5,3,4,2,2,2,2,5};
   int n = sizeof(a) / sizeof(a[0]);
   cout << solution(a, n) << endl;
   return 0;
}

結果如下 (經檢驗無誤)：

log, i=0, count=0, value=6
log, i=1, count=1, value=6
log, i=2, count=0, value=6
log, i=3, count=1, value=5
log, i=4, count=0, value=5
log, i=5, count=1, value=4
log, i=6, count=0, value=4
log, i=7, count=1, value=2
log, i=8, count=2, value=2
log, i=9, count=3, value=2
2

好的，先說這麼多，希望大家在刷題過程中，獲得啓發，舉一反三，融會貫通，有所進步，拿到更多更好的 offer, 薪資翻倍。

外界有點喧囂和浮躁，然而我們可以稍微寧靜一下，安心學習和積累，學習本身就是一件很純粹快樂的事情，誰說不是呢？

你好，我是濤哥，CSDN 排名第一。

自學計算機，畢業後就職華爲騰訊。

從事軟件開發，期待與你一起成長。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/IkGj0G0aDXKcQ-XJcyRIjw

猜你喜歡