Epoch

題目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

題意

一個陣列中，找出出現超過⌊ n/2 ⌋次的數字。

想法

1 比較笨的

設一個陣列，當出現不同數字就放進陣列，再另外設一個陣列紀錄出現次數，最後找出符合條件的數字。

2 比較聰明的

一個數字在此陣列會超過一半，表示可以將第一個數字當作是此數字，並開始計算它的次數，遇到與他相同的就+1，不同就-1，當次數累積到-1時，就換一個key

code 1

int majorityElement(int* nums, int numsSize) {
    int i;
    int j;
    int repeat_flag = 0;
    int cnt = 0;
    int save = 0;
    int array[numsSize];
    int times[numsSize];
    for(i=0; i<numsSize; i++){
        array[i]=0;
        times[i]=0;
    }
    for(i=0; i<numsSize; i++) {
        repeat_flag = 0;
        for(j=0; j<cnt; j++) {
            if(nums[i] == array[j]) {
                repeat_flag = 1;
                times[j]++;
                break;
            }
        }
        if (repeat_flag != 1) {
            array[cnt] = nums[i];
            times[cnt++]++;
        }
    }
    for(i=0; i<cnt; i++) {
        if (times[i]>numsSize/2)
            save = array[i];
    }
    return save;

}

code2

int majorityElement(int* nums, int numsSize) {
    int i;
    int key = nums[0];
    int count = 1;
    for(i=1; i<numsSize; i++) {
        if (nums[i] == key)
            count++;
        else {
            count--;
            if (count<0) {
                key = nums[i];
                count = 1;
            }
                
        }
    }
    return key;

}