两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
//哈希表做法
function twoSum(nums, target) {
let obj = new Map();
for (let i = 0; i < nums.length; i++) {
// 计算需要的另一个值
const complement = target - nums[i];
// 如果哈希表中有这个值，返回两个索引
if (obj.has(complement)) {
return [obj.get(complement), i]; // 返回两个索引
}
obj.set(nums[i], i);
}
return [];
}
//双for循环
只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
//哈希表做法
function appearOnce(nums){
let obj = new Map()
for(let num of nums){
obj.set(num,(obj.get(num)|| 0) + 1)
}
for (const [key, value] of obj.entries()) {
if (value === 1) {
return key; // 频率为1的元素就是只出现一次的元素
}
}
return null
}
多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
//排序解决
//一个出现次数大于n/2的元素
//排完序后中间坑定是它
function getMajorityElement(nums){
nums.sort((a,b)=>a-b)
return nums[Math.floor(nums.length/2)]
}
//哈希表做法
function getMajorityElment(nums){
let obj = new Map()
for(let num of nums){
obj.set(num,(obj.get(num)||0) + 1)
}
for (const [key, value] of obj.entries()) {
if (value > nums.length / 2) {
return key;
}
}
return null
}
const arr = [1,1,1,2,2,2,2]
console.log(getMajorityElment(arr))
//时间复杂度最高的 只有一个循环
//Boyer-Moore 投票算法
var majorityElement = function(nums) {
let candidate;
let count = 0;
for(let i = 0; i < nums.length; i++){
if(count === 0){
candidate = nums[i]
}
if(nums[i] === candidate){
count++
}else{
count--
}
}
return candidate
};