Java教程

《编程之美》2.3 寻找发帖“水王” ( 寻找数组中数量超过数组一半的元素)

本文主要是介绍《编程之美》2.3 寻找发帖“水王” ( 寻找数组中数量超过数组一半的元素),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:
在数组中,有一个元素的数量超过了数组元素整体数量的一半,请找出该元素

#include <iostream>

// 摩尔投票法: 
//    由于目标元素在数组中超过了一半,因此如果从数组中任意取出两个不同的元素一起丢掉,则最后剩余的元素肯定为目标元素, 因为
//       1. 如果取出的是非目标元素的其中的两个元素,那么”扔掉“这个行为不会影响最终的剩余元素为目标元素
//       2. 如果取出的元素为目标元素和一个非目标元素,则最终目标元素也会剩余,即,在非目标元素联合起来一起”消除“目标元素的最坏情况下,目标元素也会胜出。
// 函数执行过程说明:
//       1. 取出第一个元素,将其做为目标元素的候选,然后取后面的元素,如果相同,则给这个"候选目标元素”数量+1,
//       2. 如果取出的元素如果不相同,则将“候选目标元素”的数量-1,直到其数量为0,就失去了作为“目标元素”候选的资格,
//       3. 当候选目标元素失去候选资格后,将新出现的元素作为新的候选目标元素,重复上面过程
int find( int arr[], int length ) 
{
    int candidate = arr[0]; 
    int candidateCount = 1; 
    for ( int i = 1; i < length; i++ ) {
        if ( arr[i] == candidate ) {
            candidateCount++; 
        }
        else {
            if ( candidateCount == 0 ) {
                candidate = arr[i]; 
                candidateCount++; 
            }
            else {
                candidateCount--; 
            }    
        }
    }
    return candidate;  
}



int main( int argc, char** argv )
{
    // 寻找数组中数量超过一般的元素 
    // 对于如下示例,应该返回元素3,因为元素3的个数超过了一半 
    int arr[] = { 3, 1, 9, 1, 1, 2, 1, 3, 4, 1, 1, 1, 5}; 
    int length = sizeof (arr) / sizeof (arr[0]); 
    std::cout << "1. array length is " << length << std::endl; 
    std::cout << " the element " << find(arr, length) << " has over half size of the array" << std::endl; 

    return 0; 
}

 

这篇关于《编程之美》2.3 寻找发帖“水王” ( 寻找数组中数量超过数组一半的元素)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!