就是一个sorted list，找popular value（定义为出现次数 > N／4），然后问了我会拿什么test case去test，然后让我问问题。

Method 1: Traverse array with pointer (time: O(n), space: O(n))

• Starting from the first element, increment the pointer and a counter if the next element is the same as the current element.
• Check if counter is greater than N/4
• Increment the counter until it reaches the length of the array.

def marjority(arr):
  output = []
  if arr:
    size = len(arr) / 4
    i = 0
    while i < len(arr):
      count = 1
      cur = arr[i]
      while i < len(arr) - 1 and arr[i + 1] == cur:
        count += 1
        i += 1
      if count > size:
        output.append(cur)
      i += 1
  return output

print(marjority([0,1,1,1,1,1,1,3,3,5,5,5,5,18,19]))
print(marjority([]))
print(marjority([0,1]))

# return -1 if x doesn't exist in arr
def binary_search(arr, x):
    pos = bisect.bisect_left(arr, x)
    return pos if pos != len(arr) and arr[pos] == x else -1

def majority(arr):
    n = len(arr)
    output = []
    quarters = [arr[n/4],arr[n/2],arr[3*n/4]]

    # avoid repeating answer
    if arr[n/4] == arr[n/2]:
        quarters.remove(arr[n/4])
        quarters.remove(arr[n/2])
        output.append(arr[n/2])
    if arr[n/2] == arr[3*n/4]:
        if arr[n/2] in quarters:
            quarters.remove(arr[n/2])
        if arr[3*n/4] in quarters:
            quarters.remove(arr[3*n/4])
        if arr[n/2] not in output:
            output.append(arr[n/2])

    for quarter in quarters:
        pos = binary_search(arr, quarter)
        if pos != -1 and pos+n/4 < len(arr) and arr[pos] == arr[pos+n/4]:
            output.append(arr[pos])
    return output

print(majority([1,1,6,6,6,6,9,145]))
print(majority([0]))