面试题39：数组中出现次数超过一半的数字

标签：eth   mes   试题   efi   lock   rap   return   超过   数字   

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路

• 排序后遍历（相当于简化后的暴力）O(logn)
• 数组特点O(n)

上代码（C++香）

法一：排序后遍历（相当于简化后的暴力）

#include 
#include 
#include 
#include 
#include "ListNode.h"
#include "TreeNode.h"
#include "Graph.h"
using namespace std;

#define MAXNUM 100010
#define DRIFT 1001

void mySwap(vector &num, int i, int j){
    int temp = num[j];
    num[j] = num[i];
    num[i] = temp;
}

int myPartition(vector &num, int low, int high){
    int pivot = num[low];
    while(low = pivot)
            high--;
        mySwap(num, low, high);
        while(low  &num, int low, int high){
    if(low >= high)
        return ;
    int pivot = myPartition(num, low, high);
    QSort(num, low, pivot - 1);
    QSort(num, pivot + 1, high);
}

// 已排序的数组
int MoreThanHalfNum_Solution(vector numbers) {

    // 先排序
    QSort(numbers, 0, numbers.size() - 1);
    for(int i = 0; i  numbers;
    numbers.push_back(1);
    numbers.push_back(2);
    numbers.push_back(3);
    numbers.push_back(2);
    numbers.push_back(2);
    numbers.push_back(2);
    numbers.push_back(5);
    numbers.push_back(4);
    numbers.push_back(2);
    cout

面试题39：数组中出现次数超过一半的数字

标签：eth   mes   试题   efi   lock   rap   return   超过   数字   

原文地址：https://www.cnblogs.com/flyingrun/p/13525318.html