Leetcode:169.Majority Element

Posted on | Comments: | Views:
Array;Divide and Conquer

169.Majority Element

题目理解:

找出数组中出现次数大于 n/2 的数字

思路:

整体基于分治法的思想, 将数组分为三部分.

  • 1.随机选择一个数 v
  • 2.将数组分为 <v, =v, >v 三部分
  • 3.若 sizeof(=v) > n/2, 既满足要求, 则找到; 否则, 从剩下两个小数组中选取较大的一个重复步骤1 2 3

小结:

本周算法课刚好在讲分治法, 而刚好碰到类似的题, 便写了下来.
时间复杂度大概为 O(n)

Submission Detail:

Detail

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int find(int* a, int size, int majority) {
    int mid = a[rand()%size];
    int* small = (int*)malloc(size*sizeof(int));
    int* big = (int*)malloc(size*sizeof(int));
    int smallSize = 0, bigSize = 0, equal = 0;
    for (int i = 0; i < size; ++i) {
        if (a[i] == mid) {
            equal++;
        } else if (a[i] < mid) {
            small[smallSize++] = a[i];
        } else if (a[i] > mid) {
            big[bigSize++] = a[i];
        }
    }
    if (equal > majority) {
        return mid;
    } else {
        if (smallSize < bigSize) {
            return find(big, bigSize, majority);
        } else {
            return find(small, smallSize, majority);
        }
    }
}

int majorityElement(int* nums, int numsSize) {
    return find(nums, numsSize, numsSize/2);
}