169.Majority Element

这是leetCode第169题

题目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

意思是说：给你一个大小为n的数组，找到majorityElement,该元素在数组中的出现次数超过n/2次（因此n为奇数）。
你可以假设数组不是空数组，和majorityElement元素总是存在。
也就是说，测试用例的数组中总是存在我们要找到的元素。

我的思路

既然数组中一定存在majorityElement元素，那么如果我们给数组进行排序，那么数组的中间的一个元素就是majorityElement；

因为我的代码如下：

//题目中提示，数组不为空，目标一定存在，所以代码可以这么写。
var majorityElement = function(nums) {
    var n = Math.floor(nums.length/2);
    nums.sort(function(a,b){
        return a-b;
    });
    return nums[n];
};

虽然方法写出来了，但是我用了数组的sort方法，因此我的算法的时间复杂度为O( nlog2(n) )*。

还有一种更快的算法，时间复杂度为O(n);

下面这种算法，是我从别人那学来的：

var majorityElement = function(nums) {
    var major = '';
    var count = 0;
    var length = nums.length;
    for(var i=0; i<length; i++) {
        if (count === 0) {
            major = nums[i];
            count =1;
        } else if(nums[i] === major) {
            count++;
        } else {
            count--;
        }
    }
    return major;
}  ;

该算法假设每个元素都有可能是majorityElement。当count===0时，就更新majorityElement。如果第i 个元素==major,count就加1，否则就减1。

因为majorityElement元素的次数大于n/2，所以当某个元素被假设为majorityElement时，真正的majorityElement都总能把count减为0，最后真正的majorityElement就一定会上位。

举个例子：

  [2,3,2,3,2]  
  //count变化=> 1,0,1,0,1
 // major变化=> 2,2,2,2,2 

[2,2,2,2,3,3,4]
//count变化=>1,2,3,4,3,2,1
//major变化=>2,2,2,2,2,2,2

对比两个算法的速度

执行下面的代码，来生成一个模块Array.js，该模块导出一个长度为200001的数组，数组中一定存在majorityElement。

node product.js

product.js的代码如下：

var fs = require("fs");
var nums =[];
var boundary = 100000;
for(var i=0;i<boundary;i++){
    nums.push(i);
}
//确认一个随机的majorityElement
var random = Math.floor(Math.random()*boundary);
//然后把majorityElement，随机插入数组中，boundary+1次
//这样majorityElement出现次数肯定超过n/2
for(var i=0;i<=boundary;i++){
      nums.splice(Math.floor(Math.random()*boundary),0,random);
}
//转成字符串，注意字符串“module.exports=array"
//这样就会生成一个模块，供其他文件加载。
var str = "var array=["+nums+"];module.exports=array;";
//写入Array.js文件，生成了js代码
fs.writeFile('Array.js', str,  function(err) {
   if (err) {
       return console.error(err);
   }
   console.log("数据写入成功！");
 });

数组有了，我们开始测试算法的速度。

首先测试我写的算法：

 //导入数组
 var nums = require('./Array.js');
 var start = new Date().getTime();
 console.log("majorityElement : "+majorityElement(nums));
 var end = new Date().getTime();
 console.log("time: "+(end-start));

测试结果：

majorityElement : 13424
time: 57

测试别人的算法：

  //导入数组
  var nums = require('./Array.js');
  var start = new Date().getTime();
  console.log("majorityElement : "+majorityElement(nums));
  var end = new Date().getTime();
  console.log("time: "+(end-start));

测试结果：

  majorityElement : 13424
  time: 18

对比一下，57毫秒明显比18毫秒时间长，看来第二种算法的速度明显比我快。

虽然我的算法速度慢，但是我从别人那里学到了新的方法，总体来讲还是挺满足的，因为有了新收获。