Loading... 今天遇到了一道题!题目如下: <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-62831fdf05740eb432ea6697b83fe03077" aria-expanded="true"><div class="accordion-toggle"><span>题目</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-62831fdf05740eb432ea6697b83fe03077" class="collapse in collapse-content"><p></p> 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗? 示例 1: 输入: [2,2,1] 输出: 1 示例 2: 输入: [4,1,2,1,2] 输出: 4 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/single-number 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 <p></p></div></div></div> ## 我的思路: 给数组使用快速排序法,然后用双指针遍历数组,前后不相同的数即为目标值! 快速排序法时间复杂度O(log n), 遍历数组 O(n),显然已经不符合题意 ->算法应该具有线性时间复杂度。(O(n))。 思来想去想不到解决方法! 我偷看了一些评论,评论说用到异或运算,以前没有接触过,于是我决定查看官方答案! ## 答案: ```cpp class Solution { public: int singleNumber(vector<int>& nums) { int ret = 0; for (auto e: nums) ret ^= e; return ret; } }; ``` ### 异或运算: `^ ` 这个运算符叫 `异或运算符` 异或运算有以下三个性质。 任何数和 0 做异或运算,结果仍然是原来的数,即:a ^0 = a; 任何数和其自身做异或运算,结果是 0,即:a^a = 0; 异或运算满足交换律和结合律,即:a^a^0^a = a; ### auto的用法: `for (auto x : nums)` 作用:遍历数组nums,并且每一次遍历得到的值 赋值给 x; 相当于: ```cpp for(int i = 0; nums[i] != '\0'; i++) { int x = nums[i]; } ``` 最后修改:2021 年 09 月 14 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果文章有用,请随意打赏。
5 条评论
for (auto x : nums) 是C11,dev c++ 默认c99. (ó﹏ò。)
我就说我以前从来没用过
auto 的作用仅仅是判断 初始化右值的类型,让左值匹配。不是“遍历数组nums,并且每一次遍历得到的值 赋值给 x”。for (auto x : nums)才是这个功能
for(int x:nums),也是可以的,只是auto x 判断了x的类型,在预处理的时候判断的,不会影响运行时间。
在C++ 容器里面常用,因为有些容器类型比较长。
牛蛙!get到了!