跟我一起刷leetCode算法题4之Majority Eleme
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毫秒时间长,看来第二种算法的速度明显比我快。
虽然我的算法速度慢,但是我从别人那里学到了新的方法,总体来讲还是挺满足的,因为有了新收获。