分而治之的策略来确定列表中是否有超过 1/3 的相同元素

Question

我正在使用分而治之的算法来确定列表中是否有超过 1/3 的元素相同。例如：[1,2,3,4] 不，所有元素都是唯一的。[1,1,2,4,5] 是的，其中 2 个是相同的。

没有排序，是否有分而治之的策略？一直纠结于怎么分...

def is_valid(ids): 

    n = len(ids) 

    is_valid_recur(ids, n n-1)

def is_valid_recur(ids, l, r):

    m = (l + h) // 2

    return ....  is_valid_recur(ids, l, m) ...is_valid_recur(ids, m+1, r):

Answer 1

这是我为了好玩而尝试的草稿。看起来分而治之可能会减少候选频率检查的数量，但我不确定（请参见最后一个示例，其中仅针对完整列表检查 0）。如果我们将列表分成三份，有效候选人可以拥有的最小频率是每个部分的 1/3。这缩小了我们在其他部分中搜索的候选列表。让f(A, l, r)代表可能在其父组中具有 1/3 或更多频率的候选人。然后：from math import ceildef f(A, l, r):&nbsp; length = r - l + 1&nbsp; if length <= 3:&nbsp; &nbsp; candidates = A[l:r+1]&nbsp; &nbsp; print "l, r, candidates: %s, %s, %s\n" % (l, r, candidates)&nbsp; &nbsp; return candidates&nbsp; i = 0&nbsp; j = 0&nbsp; third = length // 3&nbsp; lg_third = int(ceil(length / float(3)))&nbsp; sm_third = lg_third // 3&nbsp; if length % 3 == 1:&nbsp; &nbsp; i, j = l + third, l + 2 * third&nbsp; elif length % 3 == 2:&nbsp; &nbsp; i, j = l + third, l + 2 * third + 1&nbsp; else:&nbsp; &nbsp; i, j = l + third - 1, l + 2 * third - 1&nbsp; left_candidates = f(A, l, i)&nbsp; middle_candidates = f(A, i + 1, j)&nbsp; right_candidates = f(A, j + 1, r)&nbsp; print "length: %s, sm_third: %s, lg_third: %s" % (length, sm_third, lg_third)&nbsp; print "Candidate parts: %s, %s, %s" % (left_candidates, middle_candidates, right_candidates)&nbsp; left_part = A[l:i+1]&nbsp; middle_part = A[i+1:j+1]&nbsp; right_part = A[j+1:r+1]&nbsp; candidates = []&nbsp; seen = []&nbsp; for e in left_candidates:&nbsp; &nbsp; if e in seen or e in candidates:&nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; seen.append(e)&nbsp; &nbsp; count = left_part.count(e)&nbsp; &nbsp; if count >= lg_third:&nbsp; &nbsp; &nbsp; candidates.append(e)&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; middle_part_count = middle_part.count(e)&nbsp; &nbsp; &nbsp; print "Left: counting %s in middle: %s" % (e, middle_part_count)&nbsp; &nbsp; &nbsp; if middle_part_count >= sm_third:&nbsp; &nbsp; &nbsp; &nbsp; count = count + middle_part_count&nbsp; &nbsp; &nbsp; right_part_count = right_part.count(e)&nbsp; &nbsp; &nbsp; print "Left: counting %s in right: %s" % (e, right_part_count)&nbsp; &nbsp; &nbsp; if right_part_count >= sm_third:&nbsp; &nbsp; &nbsp; &nbsp; count = count + right_part_count&nbsp; &nbsp; &nbsp; if count >= lg_third:&nbsp; &nbsp; &nbsp; &nbsp; candidates.append(e)&nbsp; seen = []&nbsp; for e in middle_candidates:&nbsp; &nbsp; if e in seen or e in candidates:&nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; seen.append(e)&nbsp; &nbsp; count = middle_part.count(e)&nbsp; &nbsp; if count >= lg_third:&nbsp; &nbsp; &nbsp; candidates.append(e)&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; left_part_count = left_part.count(e)&nbsp; &nbsp; &nbsp; print "Middle: counting %s in left: %s" % (e, left_part_count)&nbsp; &nbsp; &nbsp; if left_part_count >= sm_third:&nbsp; &nbsp; &nbsp; &nbsp; count = count + left_part_count&nbsp; &nbsp; &nbsp; right_part_count = right_part.count(e)&nbsp; &nbsp; &nbsp; print "Middle: counting %s in right: %s" % (e, right_part_count)&nbsp; &nbsp; &nbsp; if right_part_count >= sm_third:&nbsp; &nbsp; &nbsp; &nbsp; count = count + right_part_count&nbsp; &nbsp; &nbsp; if count >= lg_third:&nbsp; &nbsp; &nbsp; &nbsp; candidates.append(e)&nbsp; seen = []&nbsp; for e in right_candidates:&nbsp; &nbsp; if e in seen or e in candidates:&nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; seen.append(e)&nbsp; &nbsp; count = right_part.count(e)&nbsp; &nbsp; if count >= lg_third:&nbsp; &nbsp; &nbsp; candidates.append(e)&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; left_part_count = left_part.count(e)&nbsp; &nbsp; &nbsp; print "Right: counting %s in left: %s" % (e, left_part_count)&nbsp; &nbsp; &nbsp; if left_part_count >= sm_third:&nbsp; &nbsp; &nbsp; &nbsp; count = count + left_part_count&nbsp; &nbsp; &nbsp; middle_part_count = middle_part.count(e)&nbsp; &nbsp; &nbsp; print "Right: counting %s in middle: %s" % (e, middle_part_count)&nbsp; &nbsp; &nbsp; if middle_part_count >= sm_third:&nbsp; &nbsp; &nbsp; &nbsp; count = count + middle_part_count&nbsp; &nbsp; &nbsp; if count >= lg_third:&nbsp; &nbsp; &nbsp; &nbsp; candidates.append(e)&nbsp; print "l, r, candidates: %s, %s, %s\n" % (l, r, candidates)&nbsp; return candidates#A = [1, 1, 2, 4, 5]#A = [1, 2, 3, 1, 2, 3, 1, 2, 3]#A = [1, 1, 1, 1, 1, 2, 2, 2, 2, 3]A = [2, 2, 1, 3, 3, 1, 4, 4, 1]#A = [x for x in range(1, 13)] + [0] * 6print f(A, 0, len(A) - 1)

Answer 2

您可以使用二叉搜索树 (BST)。1. 创建 BST，维护每个节点的密钥计数 2. 遍历树以使用分治法找到最大密钥计数 3. 测试 max count > n/3 使用 BST 中的数据，分治法很简单，因为我们只需要确定是否左、当前或右分支具有最高的重复次数。# A utility function to create a new BST node&nbsp;&nbsp;class newNode:&nbsp;&nbsp;&nbsp; &nbsp; # Constructor to create a new node&nbsp;&nbsp;&nbsp; &nbsp; def __init__(self, data):&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; self.key = data&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; self.count = 1&nbsp; &nbsp; &nbsp; &nbsp; self.left = None&nbsp; &nbsp; &nbsp; &nbsp; self.right = None# A utility function to insert a new node&nbsp;&nbsp;# with given key in BST&nbsp;&nbsp;def insert(node, key):&nbsp;&nbsp; &nbsp; # If the tree is empty, return a new node&nbsp;&nbsp;&nbsp; &nbsp; if node == None:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; k = newNode(key)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return k&nbsp;&nbsp; &nbsp; # If key already exists in BST, increment&nbsp;&nbsp; &nbsp; # count and return&nbsp;&nbsp;&nbsp; &nbsp; if key == node.key:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; (node.count) += 1&nbsp; &nbsp; &nbsp; &nbsp; return node&nbsp;&nbsp; &nbsp; # Otherwise, recur down the tree&nbsp;&nbsp;&nbsp; &nbsp; if key < node.key:&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; node.left = insert(node.left, key)&nbsp;&nbsp;&nbsp; &nbsp; else:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; node.right = insert(node.right, key)&nbsp;&nbsp; &nbsp; # return the (unchanged) node pointer&nbsp;&nbsp;&nbsp; &nbsp; return node&nbsp;# Finds the node with the highest count in a binary search treedef MaxCount(node):&nbsp; if node == None:&nbsp; &nbsp; return 0, None&nbsp; else:&nbsp; &nbsp; left = MaxCount(node.left)&nbsp; &nbsp; right = MaxCount(node.right)&nbsp; &nbsp; current = node.count, node&nbsp; &nbsp; return max([left, right, current], key=lambda x: x[0])def generateBST(a):&nbsp; root = None&nbsp; for x in a:&nbsp; &nbsp; root = insert(root, x)&nbsp; return root# Driver Code&nbsp;if __name__ == '__main__':&nbsp;&nbsp; &nbsp; a = [1, 2, 3, 1, 1]&nbsp; &nbsp; root = generateBST(a)&nbsp; &nbsp; cnt, node = MaxCount(root)&nbsp; &nbsp; if cnt >= (len(a) // 3):&nbsp; &nbsp; &nbsp; print(node.key)&nbsp; # Prints 1&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; print(None)用于 n/3的非分而治之技术，具有来自https://www.geeksforgeeks.org/n3-repeated-number-array-o1-space/的 O(n) 时间：# Python 3 program to find if&nbsp;&nbsp;# any element appears more than&nbsp;# n/3.&nbsp;import sys&nbsp;def appearsNBy3(arr, n):&nbsp;&nbsp; &nbsp; count1 = 0&nbsp; &nbsp; count2 = 0&nbsp; &nbsp; first = sys.maxsize&nbsp;&nbsp; &nbsp; second = sys.maxsize&nbsp;&nbsp; &nbsp; for i in range(0, n):&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # if this element is&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # previously seen,&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # increment count1.&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; if (first == arr[i]):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count1 += 1&nbsp; &nbsp; &nbsp; &nbsp; # if this element is&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # previously seen,&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # increment count2.&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; elif (second == arr[i]):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count2 += 1&nbsp; &nbsp; &nbsp; &nbsp; elif (count1 == 0):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count1 += 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; first = arr[i]&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; elif (count2 == 0):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count2 += 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; second = arr[i]&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # if current element is&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # different from both&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # the previously seen&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # variables, decrement&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # both the counts.&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count1 -= 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count2 -= 1&nbsp; &nbsp; count1 = 0&nbsp; &nbsp; count2 = 0&nbsp; &nbsp; # Again traverse the array&nbsp;&nbsp; &nbsp; # and find the actual counts.&nbsp;&nbsp; &nbsp; for i in range(0, n):&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; if (arr[i] == first):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count1 += 1&nbsp; &nbsp; &nbsp; &nbsp; elif (arr[i] == second):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count2 += 1&nbsp; &nbsp; if (count1 > n / 3):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return first&nbsp;&nbsp; &nbsp; if (count2 > n / 3):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return second&nbsp;&nbsp; &nbsp; return -1# Driver code&nbsp;arr = [1, 2, 3, 1, 1 ]&nbsp;n = len(arr)&nbsp;&nbsp;print(appearsNBy3(arr, n))&nbsp;