c++分治法求数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

解法一：排序法

先将数组排序，由于该数字出现的次数超过数组长度的一半，所以排序后中间的数一定是该数字。

时间复杂度：O(nlogn)

解法二：哈希表法

遍历数组，将每个数字出现的次数存入哈希表中，最后遍历哈希表找到出现次数超过数组长度一半的数字。

时间复杂度：O(n)，但需要额外的空间来存储哈希表。

解法三：摩尔投票法

由于该数字出现的次数超过数组长度的一半，所以可以使用一个计数器和一个候选数字，遍历数组，如果当前数字与候选数字相同，则计数器加1，否则计数器减1，如果计数器为0，则更新候选数字为当前数字。最后剩下的候选数字即为结果。

时间复杂度：O(n)

以下是摩尔投票法的Python代码实现：

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

相关问题

C++分治法求数组中最多的数

题目描述：

给定一个长度为n的数组，找出出现次数最多的数，如果有多个，输出任意一个即可。

算法思路：

采用分治法的思想，将数组不断划分为左右两个子区间，分别求出左子区间和右子区间出现次数最多的数，然后比较两个数的出现次数，取较大值作为当前区间的出现次数最多的数。

具体实现：

对于一个区间[l, r]，如果l=r，则该区间只有一个数，直接返回该数即可。

否则，将区间[l, r]划分为两个子区间[l, mid]和[mid+1, r]，分别递归求解左子区间和右子区间出现次数最多的数。

然后统计左子区间和右子区间出现次数最多的数的个数，比较两个数的出现次数，取较大值作为当前区间的出现次数最多的数。

最后返回当前区间的出现次数最多的数即可。

代码实现：

int a[MAXN]; // 数组a
int cnt[MAXN]; // 统计每个数出现的次数
int n; // 数组长度

// 求区间[l, r]中出现次数最多的数
int solve(int l, int r) {
if (l == r) return a[l]; // 如果区间只有一个数，直接返回该数
int mid = (l + r) >> 1; // 将区间划分为两个子区间[l, mid]和[mid+1, r]
int x = solve(l, mid); // 递归求解左子区间的出现次数最多的数
int y = solve(mid+1, r); // 递归求解右子区间的出现次数最多的数
int cnt_x = 0, cnt_y = 0; // 统计左子区间和右子区间出现次数最多的数的个数
for (int i = l; i <= r; i++) {
if (a[i] == x) cnt_x++; // 统计x的个数
else if (a[i] == y) cnt_y++; // 统计y的个数
}
if (cnt_x > cnt_y) return x; // 如果x的个数比y的个数多，返回x
else return y; // 否则返回y
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
cnt[a[i]]++; // 统计每个数出现的次数
}
int ans = 0, max_cnt = 0; // ans表示出现次数最多的数，max_cnt表示出现次数最多的数的次数
for (int i = 1; i <= n; i++) {
if (cnt[a[i]] > max_cnt) { // 如果a[i]出现的次数比当前出现次数最多的数的次数还要多
ans = a[i]; // 更新出现次数最多的数
max_cnt = cnt[a[i]]; // 更新出现次数最多的数的次数
}
}
printf("%d\n", ans); // 输出出现次数最多的数
return 0;
}

C++使用分治算法求一个数组中的最大元素，并分析时间性能

在C++中，可以使用分治法（Divide and Conquer）的思想来寻找数组中的最大元素。最常见的一种算法是“分而治之”策略，即将数组分为两半，分别找出左半部分的最大值和右半部分的最大值，然后比较这两个最大值，找出整个数组的最大值。这是一个递归的过程，直到数组只剩下一个元素，此时这个元素就是最大值。

以下是简单的递归函数实现：

int findMax(int arr[], int low, int high) {
    // Base case: 如果只有一个元素，则它是最大值
    if (low == high)
        return arr[low];

    // 中间点
    int mid = (low + high) / 2;

    // 递归地找到左右两个子数组的最大值
    int max1 = findMax(arr, low, mid);
    int max2 = findMax(arr, mid+1, high);

    // 返回两个子数组的最大值中的较大者
    return max(max1, max2);
}

**时间性能分析**：
- 时间复杂度：该算法的时间复杂度是O(n)，其中n是数组的长度。因为每个元素只被访问一次，在每一层递归中都会处理一半的元素。
- 空间复杂度：空间复杂度是O(log n)，这是由于递归调用带来的栈空间。每次递归调用需要保存一些局部变量，对于最多log n层的递归，总的空间需求是线性的。