InterviewBit – N/3 Repeat Number

Source: N/3 Repeat Number

You’re given a read only array of n integers. Find out if any integer occurs more than n/3 times in the array in linear time and constant additional space.

If so, return the integer. If not, return -1.

If there are multiple solutions, return any one.

Example :

Input : [1 2 3 1 1]
Output : 1 
1 occurs 3 times which is more than 5/3 times. 

---

解題：

1. 這題如果不考慮空間複雜度的話其實也很簡單，採用字典結構計算陣列中每個數值的出現個數後再建立迴圈檢視統計值是否有超過我們設定的門檻即可：
2. 但這樣的方式無法達到題目對空間複雜度須為常數的限制，而需要另外想其他可以單純只留下出現次數超過門檻值的方法；
3. 因題目問的是是否有單一數字出現次數佔目標陣列超過1/3的比重，而每個陣列最多就只會有2個符合這個條件的值。對此可以採用兩組數值計算當前儲存的陣列值即出現次數，並在出現這兩個值以外的狀況時減少當前目標值之累積次數。因次數佔比超過1/3比重者必定會留到迴圈結束（有興趣了解者可自行測試），後續僅需針對最後留下來的兩個值去檢定是否符合題目設定的條件即可。

Code:

class Solution:
    # @param A : tuple of integers
    # @return an integer
    def repeatedNumber(self,nums):
        nums=list(nums)
        if nums==[]:  return -1
        can1,can2,count1,count2=0,1,0,0
        for i in nums:
            if i==can1: count1+=1
            elif i==can2: count2+=1
            elif count1==0: can1,count1=i,1
            elif count2==0: can2,count2=i,1
            else:
                count1-=1
                count2-=1
        if nums.count(can1)>len(nums)/3: return can1
        if nums.count(can2)>len(nums)/3: return can2
        return -1

GitHub: GitHub