L1-Majority Element

Posted on | In |

Majority Element

描述
给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。

样例
给出数组[1,1,1,1,2,2,2]，返回 1

挑战
要求时间复杂度为O(n)，空间复杂度为O(1)

对数组排序

一般的方法就是对数组排序，然后相同的元素就会聚集在一起，这样的算法复杂度介于O(nlgn) 和O(n^2)之间。
题目给出的数组没有说是排好序的，因此我们需要给它排序。。排序的时间复杂度是O(nlogn)，再加上遍历的时间复杂度O(n)，因此总的复杂度是O(nlogn)。

总结一句话：先排序，然后取nums[n/2]。

对消法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    public int majorityNumber(List<Integer> nums) {
        // write your code here
    	int temp=nums.get(0),count=0;
    	for(int i=0;i<nums.size();i++)
    	{
    	    if(count==0) temp=nums.get(i);
    		if(temp==nums.get(i)) count++;
    		else count--;
    		
    		}
    	return temp;
    }
}

可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1。如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。

补充

java中Arrays.sort使用了两种排序方法，快速排序和优化的合并排序。

快速排序主要是对哪些基本类型数据（int,short,long等）排序， 而合并排序用于对对象类型进行排序。
使用不同类型的排序算法主要是由于快速排序是不稳定的，而合并排序是稳定的。这里的稳定是指比较相等的数据在排序之后仍然按照排序之前的前后顺序排列。对于基本数据类型，稳定性没有意义，而对于对象类型，稳定性是比较重要的，因为对象相等的判断可能只是判断关键属性，最好保持相等对象的非关键属性的顺序与排序前一直；另外一个原因是由于合并排序相对而言比较次数比快速排序少，移动（对象引用的移动）次数比快速排序多，而对于对象来说，比较一般比移动耗时。
补充一点合并排序的时间复杂度是nlogn, 快速排序的平均时间复杂度也是nlogn，但是合并排序的需要额外的n个引用的空间

可参考
https://www.jianshu.com/p/73625dd9ac65
http://www.cnblogs.com/theskulls/p/4915270.html
https://blog.csdn.net/lalor/article/details/7338497