137.只出现一次的数字Ⅱ

news/2024/11/13 15:46:45/

1.题目描述

给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1:

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

示例 2:

输入:nums = [0,1,0,1,0,1,99]
输出:99

提示:

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • nums 中,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次

2.解题思路

把数组中的每一个数字想象成二进制表示,例如nums = [1,1,1,2] = [01,01,01,10]

按照二进制从低位到高位依次统计不同位上 '1'的个数,可以看出如果某一位上 '1'的个数不是3的倍数,那么这一位一定属于出现次数位1的那个数。

于是,只需要遍历nums 32次,依次统计每一位上1的个数,如果不是3的倍数,就把这一位加进ans

3.代码实现

class Solution {public int singleNumber(int[] nums) {int ans = 0;for (int i = 0; i < 32; i++) {int cnt = 0;for (int num : nums) {cnt += (num >> i) & 1;}if (cnt % 3 != 0) {ans |= (1 << i);}}return ans;}
}


http://www.ppmy.cn/news/1501960.html

相关文章

[C++]类的自动转换和强制类型转换

在C中&#xff0c;类的自动转换&#xff08;也称为隐式转换&#xff09;和强制类型转换&#xff08;显式转换&#xff09;是面向对象编程中处理类型之间转换的两种重要机制。这些转换允许程序员定义如何在不同类型&#xff08;特别是自定义类型&#xff09;之间安全地交换数据。…

JDK新特性(Lambda表达式,Stream流)

Lambda表达式&#xff1a; Lambda 表达式背后的思想是函数式编程&#xff08;Functional Programming&#xff09;思想。在传统的面向对象编程中&#xff0c;程序主要由对象和对象之间的交互&#xff08;方法调用&#xff09;构成&#xff1b;而在函数式编程中&#xff0c;重点…

操作系统面试知识点总结5

#来自ウルトラマンメビウス&#xff08;梦比优斯&#xff09; 1 IO管理概述 1.1 I/O 设备 I/O 设备的类型分类。 1.1.1 按使用特性 人机交互类外部设备&#xff0c;例如打印机、显示器等。存储设备&#xff0c;例如磁盘、光盘等。网络通信设备&#xff0c;例如网络接口等。 1…

谷粒商城实战笔记-75-商品服务-API-品牌管理-品牌分类关联与级联更新

文章目录 一&#xff0c;引入Mybatis Plus分页插件二&#xff0c;品牌列表的模糊查询三&#xff0c;增加品牌测试数据四&#xff0c;开发后台品牌关联分类接口1&#xff0c;接口product/categorybrandrelation/catelog/list2&#xff0c;接口product/categorybrandrelation/sav…

SpringBoot上传超大文件导致OOM,完美解决办法

问题描述 上传大文件报错: Caused by: java.lang.OutOfMemoryError at java.io.ByteArrayOutputStream.hugeCapacity(ByteArrayOutputStream.java:123) ~[?:1.8.0_381] at java.io.ByteArrayOutputStream.grow(ByteArrayOutputStream.java:117) ~[?:1.8.0_381] …

网络安全相关竞赛比赛

赛事日历&#xff08;包含全国所有网络安全竞赛&#xff09; https://datacon.qianxin.com/competition/competitions https://www.ichunqiu.com/competition/all 全国网络安全竞赛 名称链接全国大学生信息安全竞赛http://www.ciscn.cn/信息安全与对抗技术竞赛&#xff08;In…

【面试题】测试工程师面试题汇总

1.测试基础 【测试基础】归纳整理2023年面试题-CSDN博客 2.性能测试 【性能测试】归纳整理2023年面试题 3.Python语言 【python】归纳整理2023年常见面试题 4.自动化 https://blog.csdn.net/weixin_46697247/article/details/133493163 5.测试用例 https://blog.csdn.…

Python进阶和高阶学习(持续更新)

Python 面向对象 创建类 # Python面向对象 # 创建类 # 使用 class 语句来创建一个新类&#xff0c;class 之后为类的名称并以冒号结尾: # class ClassName: # 类的帮助信息 #类文档字符串 # class_suite #类体 class Employee:所有员工的基类# 类变量empCount 0# 构…