LeetCode 136. 只出现一次的数字(巧用位运算)

2024-04-28 21:18

本文主要是介绍LeetCode 136. 只出现一次的数字(巧用位运算),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

题目地址:https://leetcode-cn.com/problems/single-number/

问题描述:

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

说明:

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

示例 1:

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

我的解题思路:

1.暴力解法

这种做法很简单,但是肯定是性能很差的一种做法,代码就不写了。

  1. 遍历整个数组的所有元素
  2. 如果某个数字是第一次出现,加入List
  3. 如果某个数字已经在List中,删除它
  4. 剩下的数字就是唯一的只出现一次的数字
复杂度分析:

时间复杂度:for循坏+从List中查找,时间复杂度是O(n2)

空间复杂度:需要额外的List,空间复杂度是O(n)

2.巧用异或运算

异或运算的规则是:如果不同就得1,如果相同则得0。利用这个特性,遍历异或整个数组的所有元素,那么出现次数为偶数的数字经过异或后等于0,剩下的数字即是数组中只出现一次的数字。

利用异或运算只需要一次for循坏,并且不需要额外的空间。

public static int singleNumber(int[] nums) {int result = 0;//使用异或运算,出现次数为偶数的数字经过异或后等于0,剩下的数字即是数组中只出现一次的数字for (int num : nums) {result = result ^ num;}return result;}

网上其他题解中可以学习的思路:

1. 利用HashMap:

用哈希表避免每次查找元素是否存在需要的 O(n)时间。查找性能比使用List更好。

class Solution {public int singleNumber(int[] nums) {Map<Integer, Integer> map = new HashMap<>();for (Integer i : nums) {Integer count = map.get(i);count = count == null ? 1 : ++count;map.put(i, count);}for (Integer i : map.keySet()) {Integer count = map.get(i);if (count == 1) {return i;}}return -1; // can't find it.}
}

这篇关于LeetCode 136. 只出现一次的数字(巧用位运算)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/944280

相关文章

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

使用PyTorch实现手写数字识别功能

《使用PyTorch实现手写数字识别功能》在人工智能的世界里,计算机视觉是最具魅力的领域之一,通过PyTorch这一强大的深度学习框架,我们将在经典的MNIST数据集上,见证一个神经网络从零开始学会识... 目录当计算机学会“看”数字搭建开发环境MNIST数据集解析1. 认识手写数字数据库2. 数据预处理的

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

Java数字转换工具类NumberUtil的使用

《Java数字转换工具类NumberUtil的使用》NumberUtil是一个功能强大的Java工具类,用于处理数字的各种操作,包括数值运算、格式化、随机数生成和数值判断,下面就来介绍一下Number... 目录一、NumberUtil类概述二、主要功能介绍1. 数值运算2. 格式化3. 数值判断4. 随机

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

电脑多久清理一次灰尘合? 合理清理电脑上灰尘的科普文

《电脑多久清理一次灰尘合?合理清理电脑上灰尘的科普文》聊起电脑清理灰尘这个话题,我可有不少话要说,你知道吗,电脑就像个勤劳的工人,每天不停地为我们服务,但时间一长,它也会“出汗”——也就是积累灰尘,... 灰尘的堆积几乎是所有电脑用户面临的问题。无论你的房间有多干净,或者你的电脑是否安装了灰尘过滤器,灰尘都

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (