出现一次的数字ii

[编程题]出现一次的数字ii

热度指数：25584 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现在有一个整数类型的数组，数组中只有一个元素只出现一次，其余元素都出现三次。你需要找出只出现一次的元素

数据范围：数组长度满足 $0 < n \le 4000$ ，数组中每个元素的值满足 $0 \le val \le 2147483648$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

[0,0,0,5]

输出

示例2

输入

[0]

输出

算法知识视频讲解

ZackHuang

发表于 2020-08-20 15:25:33

class Solution { public: int singleNumber(int* A, int n) { if (!A || n == 0) return 0; int result = 0; int N = 3; 展开全文

华科不平凡

发表于 2020-09-06 19:53:43

设元素中除了某个孤立数外，其他数都出现过且只出现过N次，解题方法如下：如果N为偶数，那么直接将每个元素异或后的结果即是最终结果如果N为奇数，我们可以依次判断每一位为1还是为0 本题代码如下： // // Created by jt on 2020/9/6. // class Solutio 展开全文

GreyPigeon

发表于 2021-11-03 15:57:23

因为提供的接口为指针，首先用容器进行接收，这里选择vector（也是数组）接收，然后排序，三个为一组，进行排序，如果v[i] != v[i+1],v[i]则为出现一次的数字，如果前面都没问题，则为最后元素。 public: int singleNumber(int* A, int n) { 展开全文

牛客564594591号

发表于 2022-01-06 14:54:07

import java.util.*; public class Solution { /** * * @param A int整型一维数组 * @return int整型 */ public int singleNumber(int[] A) { // write code here 展开全文

乌布雷

发表于 2021-05-31 10:57:43

题目描述：现在有一个整数类型的数组，数组中只有一个元素只出现一次，其余元素都出现三次。你需要找出只出现一次的元素注意：你需要给出一个线性时间复杂度的算法，你能在不使用额外内存空间的情况下解决这个问题么？思路：我们可以获取列表所有元素分别出现的次数，然后设定限制展开全文

萨根的喷火龙

发表于 2021-10-19 19:51:46

既然出现为三个或者一个，我们通过排序，可以直接count，但是为了节约时间。我们可以通过A[i]=A[i+1],判断出它是出现了三次的，所以可以直接讲i移后面的第三位。 def singleNumber(self , A ): # write code here 展开全文

可恶，被他装到了

发表于 2021-08-31 17:32:44

有两种方法：（1）对A进行sort排序，那么出现三次的数字就会被排在一起，例如：1,1,1,2,3,3,3。这样我们只要用指针一个个遍历过去，若A[i]=A[i+1]，则跳过下个，即i += 3，直至找到A[i]！=A[i+1]，输出A[i]即可；（2）直接依序遍历A中所有数字进行判断及运算，初始化展开全文