数组中重复元素出现最多，值最大的元素

求数组中重复元素出现最多，值最大的元素，次数相同时，取最大值，优先考虑次数。

例如：{5,3,5,1,2,4,3,4}; 返回5.

Update: 2013.Jan.4th 增加简化后的代码。

这个题方法倒是很快想出来，但是细节很有些不一样的地方，错了好几次。给出的应该是最复杂的一种输入形式。

考虑设置两个函数
g(n),表示数组中的元素input[n]，到n为止，input[n]重复出现的次数。
例如给出的输入，g(2) = 2.因为数组的下标为2的数是5,到这个数为止，5是第2次出现，所以g(2) = 2;

f(n)表示到n为止，重复次数最多，且值最大的那个数的下标。这里需要注意，我第一次f(n)直接选取的是这个数的值，并不是下标，这样就无法追踪到当前位置的数之前出现的次数了，所以是错的。只用通过下标，才能把它的数值和出现次数联系在一起。这个题目的最大的trick也就在这里。

假设f(n)已知，考虑f(n+1)：
g(n+1)>g(n),即到n+1为止，下标n+1的数出现的次数是最多的。
     f(n+1) = n+1
g(n+1)     f(n+1) = f(n)
g(n+1)==g(n) n+1 和f(n) 两个数出现的次数相同，那么选择其中数值最大的那个。
     if(input[n+1] > input[f(n)])说明 n+1的值要大
           f(n+1) = n+1
     if(input[n+1] < input[f(n)])说明 n+1的值要小，f(n+1)不变
           f(n+1) = f(n)

 

复杂度分析：

g(n)和f(n)的复杂度都是O(n),所以结果就是O(2n),不知道能不能把它减到O(n)

/*
 * =====================================================================================
 *
 * Filename: test.c
 *
 * Description:
 *
 * Version: 1.0
 * Created: 10/29/2012 11:06:16 PM
 * Revision: none
 * Compiler: gcc
 *
 * Author: [e-mail] (),
 * Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>


#include <stdio.h>
#define MAX 1000000
int test(int * input, int size){
    int count[MAX] = {0};
    int i = 0;
    int DP1[MAX] = {0};
    for(;i<size;i++){
        count[input[i]] ++;
        DP1[i] = count[input[i]];
                 printf("DP2[%d] = %d \n", i,DP1[i]);

    }
    int DP2[MAX] = {0};
    DP2[0] = 0;
    for(i =1; i<size; i++){
                 printf("DP2[%d] = %d \n", i-1,DP2[i-1]);
        if(DP1[i] < DP1[DP2[i-1]]){
            DP2[i] = DP2[i-1];
            continue;
        }
        if(DP1[i] > DP1[DP2[i-1]]){
            DP2[i] = i;
            continue;
        }
        if(DP1[i] == DP1[DP2[i-1]] && input[i]>input[DP2[i-1]]){
            DP2[i] = i;
            continue;
        }
        DP2[i] = DP2[i-1];
    }
    return input[DP2[size-1]];
}



/*
 * === FUNCTION ======================================================================
 * Name: main
 * Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    int input[] = {5,3,5,1,2,4,3,4};
    printf("%d\n", test(input, sizeof(input)/sizeof(int)));
} /* ---------- end of function main ---------- */

 

 

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000

int getNum(int *input, int size){
    if(input == NULL) return -1;
    int count[MAX] = {0};
    int ret = 0;
    int i;
    for(i=0;i<size;i++){
        count[input[i]]++;
        if(count[input[i]]>count[input[ret]] ||
                  (count[input[i]]==count[input[ret]] && input[i]>=input[ret]))
            ret = i;

    }
    return input[ret];
}


int main(){
    int input[] = {5,3,5,1,2,4,3,4,4};
    printf("%d \n", getNum(input,sizeof(input)/sizeof(int)));
}