找出一堆數中個數超過一半的數

問題描述

一堆數（例如6, 2, 2, 6, 3, 4, 6, 6, 6, 6），總共10個，其中”6“的個數超過總數的一半5，找出這個個數超過過半的那個數。

思路

從頭到尾周遊，兩個數相同接着往後周遊；否則删掉這兩個數，接着往後周遊。因為所找的那個數過半，是以不同的數相抵，抵消掉最後還會至少剩下一個那個要找的數。

圖示

代碼

<a></a>

問題複雜度分析

時間複雜度O(n)

空間複雜度O(1)

問題擴充

有1024個器件，有超過一半的是好的，剩下的那些是壞的。其中，有個驗貨機，好的和别的放在一起，好的可以識别出對方是好壞；壞的無法識别出對方好與壞（會給出任意結果），如何找出所有好的零件。

本文轉自jihite部落格園部落格，原文連結：http://www.cnblogs.com/kaituorensheng/p/3196964.html，如需轉載請自行聯系原作者