LeetCode题解：137.只出现一次的数字 II

浅浅的花香味﹌ 2023-03-14 13:59 118阅读 0赞

只出现一次的数字 II

一、LeetCode题解

瞧一瞧（求star!）

  • LeetCode题解Javascript版本：Gitbook版本传送门
  • LeetCode题解Javascript版本：CSDN传送门
  • 前端进阶笔记：Gitbook传送门

二、算法题

题目

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

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

示例 2:

  1. 输入: [0,1,0,1,0,1,99]
  2. 输出: 99

解法一 （hash）

思路

  • 一个节点同时拥有child和next节点时，我们叫他spec节点
  • 保存spec节点的next节点。利用栈，压入栈中
  • 用child节点覆盖next节点。
  • 向下遍历节点
  • 最后在链表尾部以此链接栈顶的节点。

代码

  1. var singleNumber = function(nums) { 
  2.     var obj = { }
  3.     for(let i = 0; i < nums.length; i++){ 
  4.         if(!obj[nums[i]]){ 
  5.             obj[nums[i]] = 1
  6.         }else{ 
  7.             obj[nums[i]]++
  8.         }
  9.     }
  10.     for(let key in obj){ 
  11.         if(obj[key] === 1){ 
  12.             return key
  13.         }
  14.     }
  15. };

结果

在这里插入图片描述

解法二（数学思想）

思路

  • 利用set存储数组中出现的不重复的数字
  • [ (a+b+c) * 3 - (a+a+a+b+b+b+c) ] / 2 = c

代码

  1. var singleNumber = function(nums) { 
  2.     var set = new Set()
  3.     for(let i = 0;i < nums.length; i++){ 
  4.         if(!set.has(nums[i])){ 
  5.             set.add(nums[i])
  6.         }
  7.     }
  8.     var sum = nums.reduce( function(prev, cur, index, arr){ 
  9.         return prev + cur
  10.     })
  12.     var sum1 = 0
  13.     for(let key of set.keys()){ 
  14.         sum1 += key*3
  15.     }
  16.     return (sum1 - sum)/2
  17. };

结果

在这里插入图片描述

关于我

  • decs： 19年毕业的前端开发一枚，沉迷Js
  • E-mail： webbj97@163.com
  • 个人博客： CSDN
  • GitHub： 传送门

发表评论

表情：
评论列表 （有 0 条评论，118人围观）

还没有评论，来说两句吧...

相关阅读

    相关 137. 只出现一次的数字 II

    给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实

    爱被打了一巴掌爱被打了一巴掌/ 0 赞/ 127 阅读