# 题目

## 作业描述

(16 pts.) Divide-and-Conquer An array A[1…n] is said to have a majority element if more than half of its entries are the same.

Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form “is A[i] > A[ j]?” (Think of the array elements as GIF files, say.) However you can answer questions of the form: “is A[i] = A[ j]?” in constant time.

Design a dynamic programming algorithm to solve this problem in O(nlogn) time. You may assume that n is a power of two. (Hint: the divide step is simple: just split the array into the left half and right half. How does knowing the majority elements (if they exist) of the two halves help you figure out the majority element in the whole array? Consider all the possibilities.)

1. Describe the algorithm, either in pseudo-code or English.

2. Argue why your algorithm is correct

3. Do a running time analysis of your algorithm.

# 反思

• 做作业时候觉得就不简单（好吧其实这是 leetcode 简单级别的题目，主要还是我太菜了 :cry: ）因为作业已经要求用divide and conquer 做，所以我也是直接把作业 的pseudo-code 转化成了python（一开始用java 一直编译失败，索性换成python吧 :joy: ）。
• 需要熟悉 平台 回答界面的接口，特别是java。
• 需要了解解题时候允许的库。

:joy: 万事开头难，加油！