欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

异或运算(只出现一次的数字)

程序员文章站 2022-07-15 12:24:28
...

位运算(只出现一次的数字)

(leetcode刷题总结)


目录

位运算(只出现一次的数字)

前言

一、题目示例

二、解题思路

1.异或运算

2.思维解读:

3.代码如下:

总结



前言

很早就学过位运算,但一直没用应用过,本题使用了异或运算相关性质。

一、题目示例

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

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

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

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions/xm0u83/
来源:力扣(LeetCode)

二、解题思路

1.异或运算

  • a ⊕ a = 0                相同元素异或为0,不同异或为1,任何数与0异或等于它本身

  • a ⊕ b = b ⊕ a         满足交换律

  • a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;   满足结合律

2.思维解读:

  使用异或运算结合律与交换律的性质:

1、将数组中第一个数与0异或,得到他本身。

2、继续与数组中其他数字挨个异或,

3、最后得到的数字就是出现了一次的数字

解析:有些朋友可能会陷入思维误区,性质不同异或为1,这里指的是二进制形式下的计算(这是位运算),同一个位上数字相同的都消除了。

3.代码如下:
 

class Solution {
public:
    int singleNumber(vector<int>& nums) { //数据都已经存在数组中
        int sign= 0; //定义标记符号
        for(int i=0;i<nums.size();i++)
            sign = sign^nums[i];    //异或运算的过程
        return sign;
    }
};
 

总结

已经不记得上次写博客是什么时候,今天开始记录自己的学习总结,有学习必有总结,没有发博客,说明我去玩了。。

相关标签: 算法

上一篇: 780-到达终点

下一篇: 46、到达终点