【2013年数据结构真题】

---

highlight: a11y-dark

41题

王道解析：

算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num 。然后重新计数，确认Num是否是主元素。算法可服务器托管网分为以下两步：

• 选取候选的主元素：依次扫描所给数组中的每个整数， 将第一个遇到的整数Num保存到c中， 记录Num的出现次数为1; 若遇到的下一个整数仍等于Num, 则计数加1, 否则计数减1; 当计数减到0时， 将遇到的下一个整数保存到c中，计数重新记为1, 开始新一轮计数，即从当前位置开始重复上述过程， 直到扫描完全部数组元素。

• 判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n/2, 则为主元素；否则， 序列中不存在主元素。

int Majority(int A[], int n) {
    int i, c, count = 1; //c用来保存候选主元素，count用来计数
    c = A[0];  //设置A[O]为候选主元素
    for (i = 1; i  0) //处理不是候选主元素的情况
                count-- ;
            else {//更换候选主元素， 重新计数
                c = A[i];
                count = 1;
        }
    if (count > 0)
      服务器托管网  for (i = count = 0; i  n / 2) return c; //确认候选主元素
    else return -1; //不存在主元素
}

最优解：

int find(int A[],int n){
    QuickSort(A,0,n-1);//快速排序O(nlog2n)
    int k,max=0,count=1;
    for(int i=0;imax){
                max=count;
                k=A[i];
            }
            count=1;
        }   
    }
    if(max>n/2)
        return k;
    else
        return -1;
}

暴力解1

int fun ( int A[], int n ) {
    int* B = (int*) malloc( sizeof (int) * n ) ;
    for ( int i = 0; i  0 && A[i]  max ) {
            max = B[i] ;
            k = i ;
        }
    if ( max > n / 2 )
        return k + 1 ;
    else
        return -1 ;
}

暴力解2：双层循环

• 选择数组的每一个元素i
• 统计i在整个数组出现的次数
• 如果大于n/2则返回

题目要求我们查找是否存在主元素，那可以直接定义找到为1，没找到为0，并写好注释。既然要找某个数是否满足主元素的性质，那就每个数去检查是否为主元素，要检查每个元素，则需要遍历。

int majority(int A[], n) {
    int m;
    //遍历每一个元素
    for (int i = 0; i  n / 2) { 
                //找到了主元素
                return A[m];
            }
        }
        //未找到主元素
        return -1;
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 入门 SpringCloudStream 之 RocketMq 实践全集

本文概览： 组件介绍 工作流程 文本消息+自定义信道 多主题+文本消息+自定义信道 标签过滤+获取头信息 定向的异常处理与全局异常处理 顺序消息 全局顺序消息 局部顺序消息 事务消息 当在选取队列组件的时候，通常要结合实际情况，大数据场景Kafka可能是理想的…