经典算法题之（一）------ 找出序列中的重复数字（待整理）_同一行或者同一列有没有相同的1算法题

 

 

判断一串数字中的重复数：int findDuplicated(int[] arr)

************************************************************************************************************************************

1.0：没有任何限制:arr中数字任意，找出第一个重复数

直接用Set即可

当然，这种解决方法可以用于后面所有变式

 

2.0：arr长度为n，arr中的数都是在0~n-1范围内的，有很多重复的数字，请找出第一个重复数

 

3.0:  所有数字重复2次，只有1个数字重复1次（或者所有数字重复偶数次，只有1个重复奇数次），找出这个数

 

4.0： 所有数字重复2次，只有2个数字重复1次（或者所有数字重复偶数次，只有2个数字重复奇数次），找出这两个数

 

5.0： 只有一个数字重复，找出这个数

 

 

 

6.0： 题目延伸 ---- 寻找主元素（出现次数大于N/2的数）

 

① 暴力方法：

统计每个元素的个数，一旦发现count>n/2，则停下

复杂度分析：

如果不存在，则要统计完，O(n*n) (第一次也算)

如果存在，最坏情况是全在右侧，则遍历到A[n/2 -1]的位置时才能找到，O(n(*(n/2 -1)) = O(n^2/2 - n)

显而易见，可以改进：如果遍历到A[n/2 -1]还不存在，则肯定不存在主元素。这样暴力方法的复杂度为O(n^2/2 - n)

 

       考虑这样的问题：能不能单向扫描即n-1 ，n-2，n-3 ......而不是后面的元素还回头跟前面元素比较?

       这样做的问题即：是否统计已经扫描过的元素对判定当前元素是否为主元素有没有影响？

1）  如果前面的元素跟当前元素相等，则之前已经扫描过，没有停下（每次扫描都判断>n/2?）,说明当前元素不是主元素，所以不统计之前的元素没有关系。

2）  如果前面的元素没有和当前元素相等的，则统计个数更不会影响。

        故，单向扫描即可。

        另外，是否可以可以只扫描到A[n/2 -1]? 道理和上述类似，问题变成“是否存在主元素在A[n/2 ~ n]的情况”？显而易见，不可能，主元素不可能在A[1 ~ N/2-1]都没出现过，全部分布在A[n/2 ~ n]。所以可以优化为：

A[1]:统计n次 (第一次也算)

A[2]:统计n-1次

......

A[n/2 -1]:统计n - n/2 = n/2次

O(n + n-1 + ... + n/2) = O((n+n/2)*(n/2-1)/2 ) = 3n^2/8 - 3n/4

 

② 基于排序的思想

       对于一个排好序的数组，如果存在主元素，则其n/2位置上的值肯定是主元素，反之，如果去统计A[n/2]个数<n/2，则一定不存在主元素。

故可以先给数组排好序，然后统计A[n/2]的个数。

       如果使用快排，则排序的平均复杂度O(nlogn)，为了保证达到O(nlogn)，可以使用随机快排（随机选取pivot）,统计A[n/2]个数的复杂度O(n),故复杂度为：O(n+nlogn)

       

       回到上个问题，我们真的需要将数组全部排好序吗？

       其实我们只是想找出数组的中位数，然后统计其个数是否>n/2

       问题来了，如果只是寻找数组中的中位数，则最好的算法有多快，是否能比最好的排序O(nlogn) 快？

       这样不由自主会想到一个经典问题：Top k 元素问题。

       基于随机快排的Top k算法可以达到O(n)的性能。

       这样，寻找中位数为O(n)，统计中位数个数为O(n)，总的复杂度O(2n)。

 

③ 随机化算法

     假设数组中共A{1...n}，如果存在主元素，其主元素个数为m。随机选取一个数，统计其个数，如果>n/2，则必然为主元素；如果<n/2，则有可能没有主元素，也有可能有，但是随机选取的数不是主元素。设p = m/n
则很明显，错误（明明有主元素但是却认为没有主元素）的概率为 1-p。我们可以通过对同一样例多次测试，这样可以将错误的概率减小到任意小的程度（k次测试就可以减小到(1-p)^k）。而复杂度为O(kn)

 

④ 隐藏的BOSS —— 简单的O(n)算法

     两变量，key和count， 从头遍历，如果后一个元素和前一个元素（key存）相同，则count++，如果不同count--；如果count等于0则将key 置为当前扫描到的元素。

    这样扫描结束时，如果count > 0，则key即为主元素。