题目描述：给一个整数数组，其中除了一个元素外每个元素都出现两次，找出这个只出现一次的元素。要求时间复杂度O(n)，空间O(1)。
分析：设一个数组记录每个数的出现次数如 c[nums[i]] ++，可满足线性的时间复杂度，但是空间为O(n)。或者可以先排序，在遍历一遍，若出现nums[i] != nums[i + 1] 则找到了，但是时间复杂度O(nlgn)。利用位运算的性质：
一个数异或另一个数偶数次还是原数。
任何数与0异或还是原数。
任何数与1异或是其相反数。
代码：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int x = 0;
int n = nums.size();
for (int i = 0; i < n; i++)
{
x ^= nums[i];
}
return x;
}
};
D51 136. Single Number 题目链接 136. Single Number 题目分析 返回给定数...
136. Single Number https://leetcode.com/problems/single-n...
136. Single Number Given an array of integers, every elem...
136. Single Number Description Given a non-empty array of...
题目链接：136. Single Number 题目描述 Given a non-empty array of i...
Leetcode: 136. Single NumberGiven a non-empty array of in...
Given a non-empty array of integers, every element appear...
Problem Given a non-empty array of integers, every elemen...
问题描述 Given a non-empty array of integers, every element a...
首先哈希表的做法，时间复杂度够，但是空间肯定不行： 思路2：利用异或操作。异或的性质1：交换律a ^ b = b ...
本文标题：136. Single Number
本文链接：https://www.haomeiwen.com/subject/yuqgpxtx.html
网友评论