关于leetcode:力扣之只出现一次的数字多数元素

问题形容~ 只呈现一次的数字

给定一个非空整数数组，除了某个元素只呈现一次以外，其余每个元素均呈现两次。找出那个只呈现了一次的元素。

阐明：
你的算法应该具备线性工夫复杂度。你能够不应用额定空间来实现吗？

示例 1:

 输出: [2,2,1]
输入: 1

示例 2:

 输出: [4,1,2,1,2]
输入: 4

力扣原题目地址：https://leetcode.cn/problems/…

解决方案

计划一 应用 map 统计各个项呈现的次数，看谁呈现的次数是一

var singleNumber = function (nums) {let map = new Map() // 1. 创立一个 map 用来统计数据
    for (let i = 0; i < nums.length; i++) { // 2. 遍历数组开始统计
        // 3. 一开始 map 汇合是空的，所以持续往下看
        if (map.has(nums[i])) { // 5. 后续来了一项，新来的这一项原汇合中有一样的项
            let conut = map.get(nums[i]) // 6. 就看看原汇合中这一项呈现了几次
            conut = conut + 1 // 7. 把原有次数新增一次
            map.set(nums[i], conut) // 8. 而后更新次数
        } else { // 4. 来一项，就把这一项存进 map 外面，key 是这一项，value 是这一项呈现的次数
            map.set(nums[i], 1)
        }
    }
    // 9. 通过这么一波操作，map 汇合中就记录了，各个项呈现的次数了
    for (const [key, value] of map) { // 10. 应用 forof 遍历汇合
        if (value === 1) { // 11. 看看谁呈现的次数是一次
            return key // 12. 就把对应项返回进来告知即可
        }
    }
};

当然这里也能够应用对象去统计次数，一个情理，在此不赘述

计划二 若某一项只呈现了一次则 indexof 和 lastIndexOf 值相等

• 若某个数只呈现了一次，则 indexof 和 lastIndexOf 的值必然相等
• 若某个数呈现了两次，则 indexof 和 lastIndexOf 的值必然不相等

var singleNumber = function (nums) {for (let i = 0; i < nums.length; i++) {let item = nums[i]
        if (nums.indexOf(item) === nums.lastIndexOf(item)) {return item}
    }
};

留神：indexof 和 lastIndexOf 的区别：

• indexof 查问的某个元素首次呈现的索引（从左往右查）
• lastIndexOf 某个元素最初一次呈现的地位（区别就是从右往左查）
• 二者返回的索引，都是从左往右走的索引

计划三 应用异或运算（官网举荐）

这个异或运算确实没怎么想到，异或规定，简要如下：

• 任何数值异或 0 等于数值它自身
• 两个数值的异或，雷同为 0，相异为 1

故代码如下：

var singleNumber = function (nums) {
    let val = 0; // 1. 定义初始值为 0
    nums.forEach((item) => {val = val ^ item // 2. 循环异或})
    return val // 3. 最终的值就是后果
};

问题形容~ 少数元素

这个少数元素的题目也能够应用统计次数的思路去实现

给定一个大小为 n 的数组 nums，返回其中的少数元素。少数元素是指在数组中呈现次数 大于 ⌊ n/2 ⌋ 的元素。

你能够假如数组是非空的，并且给定的数组总是存在少数元素。

示例 1：

 输出：nums = [3,2,3]
输入：3

示例 2：

 输出：nums = [2,2,1,1,1,2,2]
输入：2

力扣原题目地址：https://leetcode.cn/problems/…

解决方案

计划一，应用 map 统计次数，并比照是否大于数组长度的一半

var majorityElement = function (nums) {let map = new Map()
    for (let i = 0; i < nums.length; i++) {if (map.has(nums[i])) {let conut = map.get(nums[i])
            conut = conut + 1
            map.set(nums[i], conut)
        } else {map.set(nums[i], 1)
        }
    }
    for (const [key, value] of map) {if (value > nums.length / 2) {return key}
    }
};

计划二，中位数断定

找法则：

如果有一个数字呈现的频率大于 n /2，也就是说，这个数字呈现了很屡次，比方有五个雪糕，有三个都是小布丁。

那么就是找到雪糕的两头数，即可找到这个呈现次数超过 n / 2 的数。所以先排序，而后再取两头数即可

var majorityElement = function (nums) {nums.sort(function (a, b) { // 1. 排个序
        return a - b
    })
    let middle = Math.floor(nums.length / 2) // 2. 取到两头数
    return nums[middle] // 3. 返回就是
}

总结

题目不难，办法有很多种，不过咱们还是要预留一种保底的办法，就是应用 map 汇合进行统计的形式。

毕竟面试中，可能比拟缓和，其余的一些形式可能想不起来了