[C++知识库]『算法研究日志Day250』简单分治 · 简单递归

众数问题

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
int a[N];
int zs, cs;
// 1 2 2    2 4 5
void range(int *a, int n, int &l, int &r)
{ // L=2  R=5   -=3没毛病（存储位置-1）
    int mid = n / 2;
    for (l = 0; l < n; l++)
        if (a[l] == a[mid])
            break;
    for (r = l + 1; r < n; r++)
        if (a[r] != a[mid])
            break;
}
void asd(int *a, int n)
{
    int l, r, mid = n >> 1;
    range(a, n, l, r);
    int same = r - l;

    if (same > cs)
        cs = same, zs = a[mid];

    if (l > cs)
        asd(a, l);
    if (n - r > cs)
        asd(a + r, n - r);
    //划分思想：左侧残部（共l个）如果比当前【最大重数】大
    //才有存在更大重数的可能性，才向下递归
    //关于范围 1 2 2      2 4 5 距离
    // L=1 R=4（实际要搜1  4

2022深度学习开发者峰会

5月20日13:00让我们相聚云端，共襄盛会！

开通VIP 解锁文章