前端JavaScript算法找出只出现一次的数字

目录
  • 题目：只出现一次的数字
  • 解法一：用 map 来解：
  • 解法二：用 异或 解

题目：只出现一次的数字

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

说明：

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

示例 1:

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

示例 2:

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

解：

第一个反应用 map 来解，时间复杂度 O(n)，是线性的，满足题意，只不过空间复杂度消耗是 O(n)，怎样降低空间复杂度，在方法二中讲；

解法一：用 map 来解：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
   let map = new Map();
    for(let i = 0; i<nums.length;i++){
        if(map.has(nums[i])){
            map.set(nums[i],map.get(nums[i])+1);
        }else{
            map.set(nums[i],1)
        }
    }
    for(let [key,value] of map.entries()){
        if(value===1){
            return key
        }
    }

};

解法二：用 异或 解

重点当然就是在怎么理解：不使用额外空间来实现

其实就是就要在数组本身上进行操作，异或操作可以帮助我们实现这一点；

异或（eor）是一个数学运算符。它应用于逻辑运算。两个相等的数异或为0；两个值不相同，则异或结果为1；一个不为0的数与0异或为这个数本身；

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
  for (var i = 1; i < nums.length; i++) {
    nums[0] = nums[0] ^ nums[i];    // 把所有的元素都异或到nums[0]上。
  }
  return nums[0];
};

以上就是前端JavaScript算法找出只出现一次的数字的详细内容，更多关于JavaScript算法只出现一次数字的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Vue中使用crypto-js AES对称加密算法实现加密解密

    Vue中使用crypto-js AES对称加密算法实现加密解密

    目录 下载crypto-js 加密解密数据 AES算法的ECB模式加密-设置秘钥 AES算法的CBC模式加密-设置秘钥和偏移量 参考: 在数字加密算法中,通过可划分为对称加密和非对称加密 对称加密:如AES,DES,3DES 含义:加密和解密使用的是同一把钥匙.密钥不能在网络中传输,避免被拦截.如果要传输,必须要对密钥进行非对称加密再加密一次. 优点:算法简单,加密解密容易,效率高,执行快. 缺点:相对来说不算特别安全,只有一把钥匙,密文如果被拦截,且密钥也被劫持,那么,信息很容易被破译. 非对

  • 利用JS实现二叉树遍历算法实例代码

    利用JS实现二叉树遍历算法实例代码

    目录 前言 一.二叉树 1.1.遍历二叉树 1.2.用js表示二叉树 1.3.前序遍历算法 1.4.中序遍历算法 1.5.后序遍历算法 1.6.按层遍历算法 二.算法题 1.1.二叉树的最大深度 1.2.二叉树的所有路径 总结 前言 在计算机科学中, 树(tree) 是一种广泛使用的抽象数据类型(ADT),是一类非线性数据结构.树在计算机领域得到广泛应用,尤其二叉树最为常用. 树的相关概念: 结点:每个元素称为结点 树根:根节点 度:一个结点含有的子结点的个数称为该结点的度 叶子节点:度为0的节

  • 前端JavaScript多数元素的算法详解

    目录 题目:多数元素 方法一:map 实现 方法二:排序 题目:多数元素 给定一个大小为 n 的数组 nums ,返回其中的多数元素.多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素. 你可以假设数组是非空的,并且给定的数组总是存在多数元素. 示例 1: 输入: nums = [3,2,3]输出: 3 示例 2: 输入: nums = [2,2,1,1,1,2,2]输出: 2 提示: n == nums.length 1 <= n <= 5 * 104 -109 <= nums

  • JavaScript数组排序的六种常见算法总结

    前言 着急用的话,选择前两个就行了,后面的看看就好. 开发中,遇到数组排序的需求很频繁,这篇文章会介绍几个常见排序思路. 一.希尔排序(性能最好) 如果要从大到小排列,则 while(arr[n] > arr[n - interval] && n > 0) . // 希尔排序算法 function xier(arr){ var interval = parseInt(arr.length / 2);//分组间隔设置 while(interval > 0){ for(var

  • 浅谈JavaScript构造树形结构的一种高效算法

    浅谈JavaScript构造树形结构的一种高效算法

    引言 我们经常会碰到树形数据结构,比如组织层级.省市县或者动植物分类等等数据.下面是一个树形结构的例子: 在实际应用中,比较常见的做法是将这些信息存储为下面的结构,特别是当存在1对多的父/子节点关系时: const data = [ { id: 56, parentId: 62 }, { id: 81, parentId: 80 }, { id: 74, parentId: null }, { id: 76, parentId: 80 }, { id: 63, parentId: 62 }, {

  • Js Snowflake(雪花算法)生成随机ID的实现方法

    Js Snowflake(雪花算法)生成随机ID的实现方法

    1.snowflake-id插件 import SnowflakeId from "snowflake-id"; const guid = num => { const id= new SnowflakeId(); return id.generate(); }; 2.原生使用 var Snowflake = /** @class */ (function() { function Snowflake(_workerId, _dataCenterId, _sequence) {

  • 前端JavaScript算法找出只出现一次的数字

    前端JavaScript算法找出只出现一次的数字

    目录 题目:只出现一次的数字 解法一:用 map 来解: 解法二:用 异或 解 题目:只出现一次的数字 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次.找出那个只出现了一次的元素. 说明: 你的算法应该具有线性时间复杂度. 你可以不使用额外空间来实现吗? 示例 1: 输入: [2,2,1]输出: 1 示例 2: 输入: [4,1,2,1,2]输出: 4 解: 第一个反应用 map 来解,时间复杂度 O(n),是线性的,满足题意,只不过空间复杂度消耗是 O(n),怎样降低

  • Python实现找出数组中第2大数字的方法示例

    本文实例讲述了Python实现找出数组中第2大数字的方法.分享给大家供大家参考,具体如下: 题目比较简单直接看实现即可,具体的注释在代码中都有: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出数组中第2大的数字 ''' def find_Second_large_num(num_list): ''''' 找出数组中第2大的数字 ''' #直接排序,输出倒数第二个数即可 tmp_list=sorted(num_lis

  • JavaScript实现找出字符串中第一个不重复的字符

    此算法仅供参考,小菜基本不懂高深的算法,只能用最朴实的思想去表达. //找出字符串中第一个不重复的字符 // firstUniqueChar("vdctdvc"); --> t function firstUniqueChar(str){ var str = str || "", i = 0, k = "", _char = "", charMap = {}, result = {name: "",i

  • Python cookbook(数据结构与算法)找出序列中出现次数最多的元素算法示例

    本文实例讲述了Python找出序列中出现次数最多的元素.分享给大家供大家参考,具体如下: 问题:找出一个元素序列中出现次数最多的元素是什么 解决方案:collections模块中的Counter类正是为此类问题所设计的.它的一个非常方便的most_common()方法直接告诉你答案. # Determine the most common words in a list words = [ 'look', 'into', 'my', 'eyes', 'look', 'into', 'my', '

  • JavaScript实现找出数组中最长的连续数字序列

    原始题目: 给定一个无序的整数序列, 找最长的连续数字序列. 例如: 给定[100, 4, 200, 1, 3, 2], 最长的连续数字序列是[1, 2, 3, 4]. 小菜给出的解法: function maxSequence(array,step){ var _array = array.slice(), //clone array _step = 1, _arrayTemp = [], i = 0; var parseLogic = { //result container parseRe

  • Go语言LeetCode题解961在长度2N的数组中找出重复N次元素

    目录 题目描述 思路分析 AC 代码 题目描述 961. 在长度 2N 的数组中找出重复 N 次的元素 给你一个整数数组 nums ,该数组具有以下属性: nums.length == 2 * n. nums 包含 n + 1 个 不同的 元素 nums 中恰有一个元素重复 n 次 找出并返回重复了 n 次的那个元素. 示例 1: 输入:nums = [1,2,3,3] 输出:3 示例 2: 输入:nums = [2,1,2,5,3,2] 输出:2 示例 3: 输入:nums = [5,1,5,

  • 如何利用C语言位运算解决只出现一次的数字

    如何利用C语言位运算解决只出现一次的数字

    解题所需要的C语言基础知识 hello!从现在开始就进入本题解的正式内容了.首先给大家用图解的方式介绍3个C语言位运算的基本操作符 & | ^ 这些知识对下面的解题都非常重要,一定要熟练掌握,不然等会会有一种"我在哪,我是谁我在干什么"的感觉. 只出现一次的数字I 题目描述 只出现一次的数字 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次.找出那个只出现了一次的元素. 说明: 你的算法应该具有线性时间复杂度. 你可以不使用额外空间来实现吗? 示例 1:

  • PHP实现找出数组中出现次数超过数组长度一半的数字算法示例

    本文实例讲述了PHP实现找出数组中出现次数超过数组长度一半的数字算法.分享给大家供大家参考,具体如下: <?php * 算法要求:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字. * * 算法分析:我们需要计算数组中每个数字的出现次数.在PHP中我们可以使用in_array函数 * 来判断一个元素是否出现在数组中.比如数组中含有1,2,3三个元素,我们要判断1是否存在 * 可以使用in_array(1,$array)来判断,但是这样只能判断1出现了一次,因为对于含有数组 * 元素1

  • C语言找出数组中的特定元素的算法解析

    问题描述:一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],其左边的数都小于等于它,右边的数都大于等于它.能否只用一个额外数组和少量其它空间实现.       思路:如果能用两个辅助数组,那么相对来说简单一点,可定义数组Min和数组Max,其中Min[i]表示自a[i]之后的最小值(包括a[i]),Max[i]表示自a[i]之前元素的最大值.有了这两个辅助数组后,对于a[i],如果它大于Max[i-1]并且小于Min[i+1],那么就符合要求.       但是题目要求是只用一个

随机推荐