首页 > 试题广场 >

只出现一次的数字(二)

[编程题]只出现一次的数字(二)
  • 热度指数：2515 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个整数数组，数组中有一个数出现了一次，其他数出现了三次，请找出只出现了一次的数。

数据范围：数组大小满足 ，数组中每个元素大小满足
示例1

输入

[1]

输出

1
示例2

输入

[1,2,2,2]

输出

1
算法知识视频讲解
添加回答
Java
牛客191072895号头像 牛客191072895号

方法1：排序

import java.util.*;
public class Solution {
    public int singleNumber (int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for(int i = 0; i < n;){
            if(i < n - 1 && nums[i] == nums[i + 1]){
                while(i < n - 1 && nums[i] == nums[i + 1]){
                    i++;
                }
            }else{
                return nums[i];
            }
            i++;
        }
        return -1;
    }
}

方法2：哈希表

import java.util.*;
public class Solution {
    public int singleNumber (int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        int n = nums.length;
        for(int i = 0; i < n; i++){
            map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
        }
        for(int key: map.keySet()){
            if(map.get(key) == 1){
                return key;
            }
        }
        return -1;
    }
}

方法3：位运算

import java.util.*;
public class Solution {
    public int singleNumber (int[] nums) {
        int[] bitNum = new int[32];
        int n = nums.length;
        for(int i = 0; i < 32; i++){
            int mask = 1 << i;
            for(int j = 0; j < n; j++){
                if((nums[j] & mask) == mask){
                    bitNum[i]++;
                }
            }
        }
        int res = 0;
        for(int i = 0; i < 32; i++){
            if(bitNum[i] % 3 != 0){
                res |= (1 << i);
            }
        }
        return res;
    }
}
发表于 2022-07-02 16:00:03 回复(0)
Java
菲尼克斯弗兰克头像 菲尼克斯弗兰克 
public class Solution {
    // 精简算法，位运算32位依次右移记录，遇到模3不为0就证明存在
    // 此时加到res上，记得也要左移保证累加的位增大就好！
    public int singleNumber (int[] nums) {
        int cnt = 0, res = 0;
        for (int i = 0; i < 32; i++) {
            cnt = 0;
            for (int n : nums) {
                cnt += n >> i & 1;
            }
            res += (cnt % 3) << i;
        }
        return res;
    }
}

发表于 2022-01-22 12:03:08 回复(0)
Java
pein531头像 pein531

1.统计词频（面试时别这么干）

统计词频的解法我就不详细说了，一行是可以解决，但这种炫技没有什么意义。笔试的时候因为赶时间，这么干也就罢了，面试这么干绝对没分。
object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param nums int整型一维数组 
        * @return int整型
    */
    def singleNumber(nums: Array[Int]): Int = {
        // write code here
        nums.map((_, 1)).groupBy(_._1).mapValues(_.size).toArray.sortBy(_._2)(Ordering[Int])(0)._1
    }
}

2.位运算

这道题在面试时正确的打开方式应该是用位运算，达成时间复杂度O(n)，空间复杂度O(1)的成就。对于32位的整型数据，我们先准备一个长度为32的数组t。这里可能有些同学会有疑问，不是说好的空间复杂度O(1)吗？为什么还要开一个辅助数组？此处的数组是32维的固定长度，与数据量n是没有关系的，因此它仍然算是有限的几个变量，空间复杂度仍然算O(1)。

2.1算法流程

  1. 遍历数组，然后将每个数的二进制表达在32个位上的值累加到辅助数组t的相应位置t[i]上。说白了，这一步就是在对整个数组统计每一位上有多少个1。
  2. 接下来我们遍历辅助数组t，如果t[i]不是3的倍数，说明那个出现一次的数在这个i位上肯定是1，否则这一位上肯定是0。通过或运算，在遍历完成后就能够得到那个只出现一次的数。
接下来解释一下原因：
对于某一个i位而言，由于存在n-1个数出现了3次，假设这些出现3次的数中，有一个数在第i位上是1，那么这一位上的1就是3次；如果有多个出现3次的数在第i位上是1，那么这一位上1的个数会以3的幅度自增，但始终都是3的倍数；如果它们之中没有一个数在第i位上是1，那么t[i]=0，仍然满足t[i]%3=0。
然后继续考虑只出现了一次的那个数。如果这个数在第i位上为1，那么累加到t[i]上就会导致t[i]%3=1；如果这个只出现一次的数在第i位上为0，无论出现3次的数在该位上是否有为1的情况，总会有t[i]%3=0成立。
因此只要通过计算t[i]%3的值就能够确定那个仅出现一次的数在这一位上是0还是1，从而还原出这个数。 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] nums) {
        // write code here
        int[] t = new int[32];
        for(int num: nums){
            for(int i = 0; i < 32; i++){
                t[i] += (num >> i) & 1;
            }
        }
        int ans = 0;
        for(int i = 0; i < 32; i++){
            if(t[i] % 3 == 1){
                ans |= (1 << i);
            }
        }
        return ans;
    }
}

2.2复杂度分析

虽然第1步统计每一位上1的个数时存在双重循环，但内层的循环次数是固定的有限次，因此这一步的时间复杂度是O(n)的。而第2步的或运算也是固定循环32次，时间复杂度是O(1)，因此算法整体的时间复杂度是O(n)。
由于只使用了有限的32个变量组成辅助数组，因此额外空间复杂度仍然是O(1)级别。

3.拓展

根据这个解法，这类问题我们可以写出一个通用版本（转自左神的算法课程），假如某个数出现了k次，而其他数出现了m次，需要注意的是：如果0出现了k次，需要特殊处理。

返回-1时是用户输入不合法的情况，可以不用考虑。
编辑于 2021-12-18 11:16:51 回复(0)
提交观点

问题信息

数组 位运算
难度：
4条回答 4046浏览

热门推荐

通过挑战的用户

查看代码

相关试题

只出现一次的数字(二)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号