乐趣区

关于leetcode:力扣之数组中数字出现的次数-II

题目形容

在一个数组 nums 中除一个数字只呈现一次之外,其余数字都呈现了三次。请找出那个只呈现一次的数字。

示例 1:

输出:nums = [3,4,3,3]
输入:4

示例 2:

输出:nums = [9,1,7,9,7,9,7]
输入:1

思路剖析

应用对象统计数字呈现的次数

思路分两步:

  • 第一步,统计值呈现的次数
  • 第二步,看看谁呈现的次数是一次
var singleNumber = function (nums) {
    /** 第一步 统计值呈现的次数 */
    let obj = {} // 1. 定义一个对象用来存储 '谁' 呈现了 '几次'
    for (let i = 0; i < nums.length; i++) {if (nums[i] in obj) { // 2. 若对象中有,就把对应次数加一,当然一开始是没有的
            obj[nums[i]] = obj[nums[i]] + 1 // 4. 比方{9:1} 变成了 {9:2} 由原来的一次,变成两次了
        } else {obj[nums[i]] = 1 // 3. 原本是空对象,当初变成{9:1} 后续若还呈现 9 就次数加一,变成{9:2}
        }
    }
    /** 第二步,看看谁呈现的次数是一次 */
    for (const key in obj) {if (obj[key] == 1) {return key}
    }
};

留神 obj 计数:咱们以 nums = [3,4,3,3] 为例,那么 obj 就变成了{3:3,4:1}

应用 Map 汇合统计数字呈现的次数

这种形式和对象形式思路相似,都是存储对应项呈现的次数,代码如下:

var singleNumber = function (nums) {
    /** 第一步 统计值呈现的次数 */
    let map = new Map() // 1. 定义一个 Map 汇合来存储
    for (let i = 0; i < nums.length; i++) {if (map.has(nums[i])) { // 2. 若 Map 汇合中有,就把对应次数加一,当然一开始是没有的
            let count = map.get(nums[i]) // 4. 有的话,先看看次数是几
            map.set(nums[i], count + 1) // 5. 而后看把次数加上一即可
        } else {map.set(nums[i], 1) // 3. 没有就存一份
        }
    }
    /** 第二步,看看谁呈现的次数是一次 */
    for (const [key, value] of map.entries()) { // 6. 最初再遍历看看谁呈现的次数是 1
        if (value == 1) {return key // 就把谁返回即可}
    }
};

大家想一下,能不能用数组去记录谁呈现的次数呢?其实这里也能够应用数组去解决。不过须要搞二维数组,因为有两个变量,谁、对应谁呈现的次数 大家能够依照这个思路尝试一下,大同小异

判断以后项是否不在余下的数组中呈现

思路很简略,举例:原数组 [6,5,5,5] 把原数组拆分成[6],[5,5,5,] 看看6 是否在余下的数组中又呈现了,如果没有在余下的数组中又呈现了,阐明 6 只呈现了一次,阐明咱们要找到就是这个6。代码如下:

var singleNumber = function (nums) {for (let i = 0; i < nums.length; i++) {let copyNums = nums.slice(0) // 1. 拷贝一份原数组
        copyNums.splice(i, 1) // 2. 拿到除去以后项以外余下项组成的数组
        let remainNums = copyNums // 3. 失去余下的数组
        if (!remainNums.includes(nums[i])) { // 4. 若以后项在余下的数组中没有再一次呈现
            return nums[i] // 5. 阐明就是它啦
        }
    }
};

不过这种形式不太好,数组的办法应用的有点多,所以性能不太高。这里提一下,只是给大家减少点思路

判断以后项的开始索引是否等于完结索引

思路:就以后题目而言,能够这样定义其中法则,例数组:[5,5,6,5]。因为 6 只有一个,所以 6 头一次呈现的地位索引是 2 最初一次呈现的索引也是2 所以判断某一项头一次呈现的地位,是否等于某一项最初一次呈现的地位即可,代码如下:

var singleNumber = function (nums) {for (let i = 0; i < nums.length; i++) {let firstTimeIndex = nums.indexOf(nums[i]) // 1. 找到首次呈现的地位
        let lastTimeIndex = nums.lastIndexOf(nums[i]) // 2. 找到最初一次呈现的地位
        if (firstTimeIndex == lastTimeIndex) { // 3. 若 首次等于最初 则就找到啦
            return nums[i] // 4. 找到返回之即可
        }
    }
};

这种形式略微好一点,不过笔者认为最好的形式,还是应用 Map 汇合的形式,效率高、执行用时和内存耗费都还不错^_^

退出移动版