寻找众数给定n个元素的数组A试用分治策略寻找A中的众数1若数组中出现频数的元素为众数请给出寻找众数问题的分治求法的伪代码描述2对上述算法的时间复杂度和空间复杂度予以分析。3若不要求众数出现频数但假定数组A中有且仅有一个数出现的频数最大那么该如何找到这个众数仅给出求解思想即可。给出正确的解答步骤

1. 分治求法的伪代码描述：

def find_majority(nums):
    if len(nums) == 1:
        return nums[0]
    
    mid = len(nums) // 2
    left_majority = find_majority(nums[:mid])
    right_majority = find_majority(nums[mid:])
    
    if left_majority == right_majority:
        return left_majority
    
    left_count = sum(1 for num in nums if num == left_majority)
    right_count = sum(1 for num in nums if num == right_majority)
    
    if left_count > len(nums) // 2:
        return left_majority
    elif right_count > len(nums) // 2:
        return right_majority
    else:
        return None

2. 时间复杂度和空间复杂度分析：

• 时间复杂度：假设数组长度为n，每次递归都将数组划分为两个子数组，则递归的深度为logn。每层递归的时间复杂度为O(n)，因为需要统计每个元素出现的次数。所以总的时间复杂度为O(nlogn)。
• 空间复杂度：递归调用的栈空间最大深度为logn，所以空间复杂度为O(logn)。

3. 若不要求众数出现频数>1，但假定数组A中有且仅有一个数出现的频数最大，可以使用Boyer-Moore投票算法来找到众数。该算法的思想是遍历数组，不断更新候选众数，当遇到其他元素时，将候选众数的票数减1，当票数为0时，更新候选众数为当前元素。遍历完数组后，候选众数即为所求。

def find_majority(nums):
    candidate = None
    count = 0
    
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif candidate == num:
            count += 1
        else:
            count -= 1
    
    return candidate

该算法的时间复杂度为O(n)，空间复杂度为O(1)