题目
思路
1)最容易想到的就是使用一个map来统计每个元素出现的次数,当前元素出现次数>(n/2) 时,就不再遍历并返回当前元素。
2)最近做的题目都是双指针,于是想着将数组进行排序后,相同的元素肯定是连续排列在一起的,使用双指针来判断每个元素出现次数,将大于n/2的元素进行返回。看了题解,发现排完序后,下标在(n/2)的元素就一定是多数元素!还得是数学!
3)看了题解的那个投票法,可以理解为:当删除两个不同元素的后,剩下的一定是多数元素。
代码
// hashmap
public int majorityElement(int[] nums) {
if(nums.length == 1){
return nums[0];
}
// 遍历数组 统计每个元素出现的次数
HashMap<Integer, Integer> map = new HashMap();
for(int item: nums){
if(!map.containsKey(item)){
map.put(item, 1);
}
else{
int occur = map.get(item) + 1;
if(occur > (nums.length / 2)){
return item;
}
map.put(item, occur);
}
}
return -1;
}
// 排序遍历 实际两行代码就可以了 排完序后返回nums[n/2]
public int majorityElement(int[] nums) {
if(nums.length == 1){
return nums[0];
}
// 排序
Arrays.sort(nums);
int slow = 0;
int fast = slow + 1;
while(fast < nums.length){
if(nums[fast] == nums[slow]){
fast ++;
}
else{
int occur = fast - slow;
if(occur > (nums.length / 2)){
return nums[slow];
}
slow = fast;
fast ++;
}
}
// 数组中一定存在多数元素 则跳出循环表示当前nums[slow]与最后一个元素都是相等的 因此返回nums[slow]
return nums[slow];
}
// 投票法
public int majorityElement(int[] nums) {
int constant = nums[0];
int times = 1;
for(int i = 1; i < nums.length; i++){
if(nums[i] == constant){
// 相同元素++ 表示多一条命 也就是可以和其他不同元素删掉删掉次数++
times ++;
}
else{
if(times == 0){
// 当前数已和其他数同归于尽 删掉了
constant = nums[i];
times = 1;
}
else{
times --;
}
}
}
return constant;
}
题目
思路
1)自己想的也是遍历,但是提交超出时间限制,而且对于循环遍历数组也没有想到取模运算。
2) 循环遍历以每个下标为起点的结果,但是下一次遍历起点是上一次终点+1
代码
int n = gas.length;
int i = 0;
while(i < n){
// 从每个节点开始遍历
int sumOfGas = 0, sumOfCost = 0;
int cnt = 0;
while(cnt < n){
// 取模运算是为了循环遍历这个数组
int j = (i + cnt) % n;
sumOfCost += cost[j];
sumOfGas += gas[j];
if(sumOfCost > sumOfGas){
break;
}
cnt ++;
}
// 走过了所有的节点
if(cnt == n){
return i;
}
else{
// 设置下一下遍历的起点为当前能够走最远的节点+1
i = i + cnt + 1;
}
}
return -1;