问题描述
一堆数（例如6, 2, 2, 6, 3, 4, 6, 6, 6, 6），总共10个，其中”6“的个数超过总数的一半5，找出这个个数超过过半的那个数。
思路
从头到尾遍历，两个数相同接着往后遍历；否则删掉这两个数，接着往后遍历。因为所找的那个数过半，所以不同的数相抵，抵消掉最后还会至少剩下一个那个要找的数。
图示
代码
#include <iostream> using namespace std; typedef struct node { int num; node *before; node *next; }node; int main() { node *p_now, *p_next; node *root = new node; p_now = root; int a[] = {6, 2, 2, 6, 3, 4, 6, 6, 6, 6}, i; for(i=0; i<10; i++) { node *p = new node; p->num = a[i]; p->next = NULL; cout << "hello" << endl; p->before = p_now; p_now->next = p; p_now = p; } p_now = root->next; p_next = p_now->next; node *p1, *p2; while(p_next != NULL) { if(p_now->num != p_next->num) { if(p_now->before != root) { p1 = p_now; p2 = p_next; p_now = p_now->before; p_next = p_next->next; p_now->next = p_next; p_next->before = p_now; } else { p1 = p_now; p2 = p_next; p_now = p_next->next; p_next = p_now->next; p_now->before = p1->before; } delete(p1); delete(p2); } else { p_now = p_next; p_next = p_now->next; } } cout << p_now->num << endl; }
问题复杂度分析
时间复杂度O(n)
空间复杂度O(1)
问题扩展
有1024个器件，有超过一半的是好的，剩下的那些是坏的。其中，有个验货机，好的和别的放在一起，好的可以识别出对方是好坏；坏的无法识别出对方好与坏（会给出任意结果），如何找出所有好的零件。
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3196964.html，如需转载请自行联系原作者
