力扣之只出现一次的数字&多数元素 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 =https://www.it610.com/article/== 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集合进行统计的方式。
【力扣之只出现一次的数字&多数元素】毕竟面试中，可能比较紧张，其他的一些方式可能想不起来了