leetcode136.只出现一次的数字[easy](python/rust)

原创

从不摸鱼的van

发布于 2023-10-20 17:24:05

1350

发布于 2023-10-20 17:24:05

最近对rust忽然升起了很大的兴趣，这个语言被誉为更好的c++，于是在~~（摸鱼）~~工作学习的时候顺便看了一下rust的基本语法，包括变量命名控制流和函数。然后到了每天的刷题时间，看到编程语言里面支持rust，所以就浅浅地写了一个题目试试水。

题目描述：

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

首先映入脑子的就是暴力法，双重循环找不同，但是细看题目要求，O(n)的时间复杂度，O(1)的空间复杂度。

如果使用双重循环很明显时间上就会不符合要求。

如果使用字典映射或者集合求存在，则需要O(n)的空间复杂度。

再次思考发现相关标签有位运算：思路一下子就清晰了，由于异或运算的结果如下： x XOR x = 0

x XOR 0 = x

所以把所有的数组元素异或即可。

题解1:使用python：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        num: int = 0
        for item in nums:
            num ^= item
        return num

题解2:使用rust：

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        let mut sum: i32 = 0 ;
        for num in nums.iter(){
            sum ^= num ;
        } 
        sum
    }
}

恐怖如斯，运行时间到了0ms，那再顺便看一下c++：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int sum = 0;
        for (int num: nums)
            sum ^= num;
        
        return sum;
    }
};

不愧被称为更好的c++，rust恐怖如斯，看来以后考虑更新rust学习笔记了～

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

leetcode

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

leetcode

登录后参与评论

0 条评论

热度