题目描述

分治求多数元素

C++ 代码

/*===============================================================
*   Copyright (C) 2021 All rights reserved.
*   
*   文件名称：demo.c
*   创 建 者：杨航
*   创建日期：2021年07月20日
*   描    述：
*
*   更新日志：
*
================================================================*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <strings.h>

int main()
{
    int a[9] = {1,1,1,2,2,1,1,1,2};
    int num = findMoreNum(a, 0, 8);
    printf("%d\n", num);
}

int findMoreNum(int arr[], int low, int high)
{
    int lNumTimes = 0;
    int rNumTimes = 0;
    if(low == high)
        return arr[low];
    /*二分法，一直递归，直到low == high*/
    int lNum = findMoreNum(arr, low, (low+high)/2);
    int rNum = findMoreNum(arr, (low+high)/2+1, high);

    /*求二分后指定元素出现的个数，返回出现次数较多的数据NUM*/
    lNumTimes = numCount(arr,lNum,low,high);
    rNumTimes = numCount(arr,rNum,low,high);
    return lNumTimes > rNumTimes? lNum : rNum;  
}

int numCount(int arr[], int num, int low, int high)
{
    int count = 0;
    int i = 0;
    for(i = low; i <= high; i++)
    {
        if(arr[i] == num)
            count++;
    }
    return count;
}