寻找发帖“水王“（分治法）

太过爱你忘了你带给我的痛 2022-11-13 04:29 176阅读 0赞

问题描述：  
有某一论坛，其中有一发帖水王，不但喜欢发帖，还会回复其他ID发的每个帖子。“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？

分析：  
其实这种问题，本质上表示为有一个数组，其中某个数据在数组中占了一半以上，试找到这个数据。

第一种方法：直接进行排序，排好序的数组的中间位置一定是这个元素。时间复杂度为O(nlogn)

第二种方法：如果每次删除两个不同的ID（不管是否包含“水王”的ID），那么，在剩下的ID列表中，“水王”ID出现的次数仍然超过总数的一半。看到这一点之后，就可以通过不断重复这个过程，把ID列表中的ID总数降低（转化为更小的问题），从而得到问题的答案，总的时间复杂度只有O（N），且只需要常数的额外内存。代码如下：

Type find(Type * ID, int N)
    { 
    	int nTimes = 0;  //初始化候选解出现的次数为0
    	int i;
    	Type candidate;   //要寻找的水王的候选解
     
    	for (i = 0; i < N; i++)  //开始遍历数组
    	{ 
    		if (nTimes == 0)  //如果上一个候选解出现的次数变为0之后
    		{ 
    			candidate = ID[i];  //令候选解为当前的ID
    			nTimes++;  //当前候选集出现的次数加1
    		}
    		else
    		{ 
    			if (candidate == ID[i])  //如果当前ID与候选解相同，则候选解出现的对应的次数加1
    				nTimes++;
    			else  //如果当前ID与候选解不同，则候选解出现的对应的次数减1
    				nTimes--;
    		}
    	}
     
    	return candidate; //返回水王
    }

注意上面的nTimes的使用非常巧妙。

扩展问题：  
如果“水王”没有了。但是有3个发帖很多的ID，发帖数目都超过了帖子总数的1/4。如何快速找出他们的ID？

分析：最初，有1个发帖超过1/2的水王，我们每次删除2个不同的ID，这样可以保证剩余的一个发帖是我们要寻找的水王；此时有3个发帖超过1/4的小水王，我们只需要每次删除4个不同的ID就可以了，这样就可以保证剩余的3个就为我们要寻找的那3个发帖。具体实现的过程如下：

void Find(Type * ID, int N)
    { 
    	Type candidate1, candidate2, candidate3;
    	int nTimes1 = 0, nTimes2 = 0, nTimes3 = 0;
    	int i;
     
    	for (i = 0; i < N; i++)
    	{ 
    		if(nTimes1 == 0)
    		{ 
    			if(ID[i] == candidate2)
    				nTimes2++;
    			else if (ID[i] == candidate3)
    				nTimes3++;
    			else
    			{ 
    				candidate1 = ID[i];
    				nTimes1++;
    			}
    		}
    		else if (nTimes2 == 0)
    		{ 
    			if(ID[i] == candidate1)
    				nTimes1++;
    			else if (ID[i] == candidate3)
    				nTimes3++;
    			else
    			{ 
    				candidate2 = ID[i];
    				nTimes2++;
    			}
    		}
    		else if (nTimes3 == 0)
    		{ 
    			if(ID[i] == candidate1)
    				nTimes1++;
    			else if (ID[i] == candidate2)
    				nTimes2++;
    			else
    			{ 
    				candidate3 = ID[i];
    				nTimes3++;
    			}
    		}
    		else
    		{ 
    			if(ID[i] == candidate1)
    				nTimes1++;
    			else if(ID[i] == candidate2)
    				nTimes2++;
    			else if(ID[i] == candidate3)
    				nTimes3++;
    			else
    				nTimes1--, nTimes2--, nTimes3--;
    		}
    	}
     
    	printf("三个水王ID分别是:%d,%d,%d\n", candidate1, candidate2, candidate3);
    }

完整代码：

#include<stdio.h>
    void Find(int * ID, int N)
    { 
    	int candidate1, candidate2, candidate3;
    	int nTimes1 = 0, nTimes2 = 0, nTimes3 = 0;
    	int i;
    
    	for (i = 0; i < N; i++)
    	{ 
    		if(nTimes1 == 0)
    		{ 
    			if(ID[i] == candidate2)
    				nTimes2++;
    			else if (ID[i] == candidate3)
    				nTimes3++;
    			else
    			{ 
    				candidate1 = ID[i];
    				nTimes1++;
    			}
    		}
    		else if (nTimes2 == 0)
    		{ 
    			if(ID[i] == candidate1)
    				nTimes1++;
    			else if (ID[i] == candidate3)
    				nTimes3++;
    			else
    			{ 
    				candidate2 = ID[i];
    				nTimes2++;
    			}
    		}
    		else if (nTimes3 == 0)
    		{ 
    			if(ID[i] == candidate1)
    				nTimes1++;
    			else if (ID[i] == candidate2)
    				nTimes2++;
    			else
    			{ 
    				candidate3 = ID[i];
    				nTimes3++;
    			}
    		}
    		else
    		{ 
    			if(ID[i] == candidate1)
    				nTimes1++;
    			else if(ID[i] == candidate2)
    				nTimes2++;
    			else if(ID[i] == candidate3)
    				nTimes3++;
    			else
    				nTimes1--, nTimes2--, nTimes3--;
    		}
    	}
    
    	printf("三个水王ID分别是:%d,%d,%d\n", candidate1, candidate2, candidate3);
    }
    
    int main()
    { 
    
        int a[16]={ 1, 2, 3, 4, 2, 3, 1, 1, 2, 3, 1, 2, 3, 1, 2, 3};
        Find(a, 16);
    }

![在这里插入图片描述][20210326102755176.png]  
参考：  
https://blog.csdn.net/qingsong3333/article/details/7392559

[20210326102755176.png]: /images/20221022/bc5c80e465704e409f120dc9d15ff21d.png