本文介绍: 不重复存储数组元素,也就是每个元素存储一次重复的不存储,计算它们的和,就相当于所有数字的两倍之和。然后将原数组中的元素全部相加,就相当于只出现了一次的元素加上全部出现了两次的元素。遍历数组中的每个数字,如果集合没有该数字,则将该数加入集合,如果集合中已经有该数字,则将该数字从集合删除最后剩下的数字就是只出现一次的数字遍历数组即可得到每个数字出现的次数,并更新哈希表,最后遍历哈希表,得到只出现一次的数字。因此,数组中的全部元素的异或运算结果即为数组中只出现一次的数字

136. 只出现一次的数字

题目

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

你必须设计实现线性时间复杂度算法解决问题,且该算法使用常量额外空间

示例

示例 1 :

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

示例 2 :

输入nums = [4,1,2,1,2]
输出:4

示例 3 :

输入nums = [1]
输出:1

提示

  • 1 &lt;= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 除了某个元素只出现一次以外,其余每个元素均出现两次

解题

如果不考虑时间复杂度空间复杂度的限制方法有很多:

方法一:集合

使用集合unordered_set存储数字遍历数组中的每个数字,如果集合没有该数字,则将该数加入集合,如果集合中已经有该数字,则将该数字从集合中删除,最后剩下的数字就是只出现一次的数字

class Solution {
public:
    int singleNumber(vector<int&gt;&amp; nums) {
        unordered_set<int&gt; numSet;
        for(int num : nums) {
            // 如果集合中已经有当前数字,则从集合中删除
            if(numSet.find(num) != numSet.end()) {
                numSet.erase(num);
            } else {
                // 如果集合中没有当前数字,则加入集合
                numSet.insert(num);
            }
        }
        // 集合中剩下的就是只出现一次的数字
        return *numSet.begin();
    }
};

方法二:哈希表法

使用哈希表存储每个数字和该数字出现的次数遍历数组即可得到每个数字出现的次数,并更新哈希表,最后遍历哈希表,得到只出现一次的数字。

class Solution {
public:
    int singleNumber(vector<int&gt;&amp; nums) {
        unordered_map<int,int&gt; numCount;
        // 遍历数组,更新哈希表中数字的出现次数
        for(int num : nums) {
            numCount[num]++;
        }
        // 遍历哈希表,找到只出现一次的数字
        for(auto&amp; pair : numCount) {
            if(pair.second == 1) {
                return pair.first;
            }
        }
        // 如果没有找到只出现一次的数字,返回默认值0
        return 0;
    }
};

方法三:元素之和两倍性质

由于集合保证元素无重复,所以使用集合unordered_set不重复的存储数组的元素,也就是每个元素只存储一次,重复的不存储,计算它们的和,就相当于所有数字的两倍之和。然后将原数组中的元素全部相加,就相当于只出现了一次的元素加上全部出现了两次的元素。如此看来,它们的差就是就差了一个只出现一次的元素了。

class Solution {
public:
    int singleNUmber(vector<int&gt;&amp; nums) {
        unordered_set<int&gt; numSet;
        int sumSet = 0;
        int sumArray = 0;
        // 遍历数组,更新集合中的元素之和和数组中的元素之和
        for(int num : nums) {
            if(numSet.find(num) == numSet.end()) {
                numSet.insert(num);
                sumSet += num;
            }
            sumArray += num;
        }
        // 计算集合中的元素之和的两倍减去数组中的元素之和,得到只出现一次的数字
        return 2*sumSet - sumArray;
    }
};

上述三种解法需要额外使用 O(n) 的空间,其中 n 是数组长度

如何才能做到线性时间复杂度和常数空间复杂度呢?

方法四:位运算(线性时间复杂度,常数空间复杂度)

异或运算有以下三个性质:

  1. 任何数和 0 做异或运算,结果仍然是原来的数,即 a⊕0=a

  2. 任何数和其自身做异或运算,结果是 0,即 aa=0。

  3. 异或运算满足交换律和结合律,即 ab⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

在这里插入图片描述

1700732089334

在这里插入图片描述

假设数组中有 2m+1 个数,其中有 m 个数各出现两次,一个数出现一次。

令 a1 、a2 、…、am为出现两次的 m 个数,am+1为出现一次的数。

根据性质 3,数组中的全部元素的异或运算结果总是可以写成如下形式:

  • (a1a1)⊕(a2a2)⊕⋯⊕(amam)⊕am+1

根据性质 2 和性质 1,上式可化简和计算得到如下结果:

  • 0⊕0⊕⋯⊕0⊕am+1=am+1

因此,数组中的全部元素的异或运算结果即为数组中只出现一次的数字。

class Solution {
public:
    int singleNumber(vector<int&gt;&amp; nums) {
        int ret = 0;
        for(auto e : nums) ret ^= e;
        return ret;
    }
};

复杂分析


**复杂分析**

- 时间复杂度:O(n),其中 n 是数组长度。只需要对数组遍历一次。
- 空间复杂度:O(1)。

原文地址:https://blog.csdn.net/m0_53485135/article/details/134593936

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_22550.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注