题目:
在数组中,有一个元素的数量超过了数组元素整体数量的一半,请找出该元素
#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; }