跟着姚桑学算法-数组中唯一只出现一次的数字

简介: 剑指offer算法

题. 数组中唯一只出现一次的数字

在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

思考题:

如果要求只使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢?

数据范围
数组长度 [1,1500]。

样例

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

输出:3

【题解】--- 状态转移

本题与上一题思路类似,上一题中,其他数都出现了两次,因此需要的状态转移方式是,如果出现两个1就抵消为0,用一个变量和异或运算即可实现,而本题是需要1出现三次时才会抵消,因此有三种状态,即1出现的次数为3k, 3k + 1, 3k + 2次

逐个位来看,要设计一个两位的状态转移,出现三个1时,循环抵消,出现0时不变,一个变量只能记录两种状态,因此要用两个变量来记录状态,用one和two两个变量来记录1出现次数
00表示1出现3k次,01表示1出现3k + 1次,10表示1出现3k + 2次

真值表

two     one     x       two     one
0       0       1       0       1   
0       1       1       1       0
1       0       1       0       0
0       0       0       0       0
0       1       0       0       1
1       0       0       1       0

先看one的状态转移方程

 one = (~one & ~two & x) | (one & ~two & ~x)
     = ~two & ((~one & x) | (one & ~x))
     = ~two & (one ^ x)

同理,再用转移后的one来求two的状态转移方程;

这里,one为当且仅当1出现次数为3k + 1, tow为当且仅当1出现次数为3k + 2;
因此如果题目改为,有一个数出现了两次,则返回two即可.

复杂度分析:

时间复杂度O(n)。

C++代码实现:

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int one=0,two=0;
        for(auto x:nums)
        {
            one=(one^x)&~two;
            two=(two^x)&~one;
        }
        return one;
    }
};
目录
相关文章
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
117 0
|
7月前
|
存储 监控 算法
关于员工上网监控系统中 PHP 关联数组算法的学术解析
在当代企业管理中,员工上网监控系统是维护信息安全和提升工作效率的关键工具。PHP 中的关联数组凭借其灵活的键值对存储方式,在记录员工网络活动、管理访问规则及分析上网行为等方面发挥重要作用。通过关联数组,系统能高效记录每位员工的上网历史,设定网站访问权限,并统计不同类型的网站访问频率,帮助企业洞察员工上网模式,发现潜在问题并采取相应管理措施,从而保障信息安全和提高工作效率。
103 7
|
8月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
323 23
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
194 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
140 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
存储 算法 Java
深入算法基础二分查找数组
文章深入学习了二分查找算法的基础,通过实战例子详细解释了算法的逻辑流程,强调了确定合法搜索边界的重要性,并提供了Java语言的代码实现。
深入算法基础二分查找数组
|
算法
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
108 0
|
算法
【算法】模拟算法——外观数组(medium)
【算法】模拟算法——外观数组(medium)
|
算法
【算法】前缀和——除自身以外数组的乘积
【算法】前缀和——除自身以外数组的乘积
124 0
|
算法
【算法】前缀和——寻找数组的中心下标
【算法】前缀和——寻找数组的中心下标

热门文章

最新文章