Given an array of integers, every element appears twice except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
这个题的意思就是:给一个数组,每个元素都重复两次,只有一个重复一次,找出这个元素. 时间复杂度O(n)，空间复杂度O(1)
解法: 利用异或:
//异或的性质1：交换律a ^ b = b ^ a，性质2：0 ^ a = a。 //由于交换律的原因,所以可以假设所有的相同的元素都相邻,nums[1]^nums[1]=0,nums[2]^nums[2]=0,所以肯定剩下一个单独的设为元素nums[i],num[i]^0=num[i]; class Solution { public: int singleNumber(vector<int>& nums) { int res = 0; for (auto num : nums) res ^= num;//解析如上 return res; } };解法2: //不知道怎么回事,无法ac
class Solution { public: int singleNumber(vector<int>& nums) { sort(nums,nums+nums.size());//排序,从小到大 int index = 0; while (index < nums.size() - 1) { if (nums[index] - nums[index+1] == 0) //如果相邻的相同,加2 { index = index + 2; } else { return nums[index];//相邻的不同,说明就是单独的一个 } } return nums[index]; } };解法3: //这个解法不合题意,时间复杂度为O(n^2);
class Solution { public: int singleNumber(int A[], int n) { vector <int> flag(n,0);//建立一个大小为n的数组,元素都为0 for(int i = 0; i < n; i++) {//遍历 if(flag[i] == 1) continue; else {//遇到0,往后找,看有没有与它相等的,如果有,那么就把两个的值都设置为1 for(int j = i + 1; j < n; j++) { if(A[i] == A[j]) { flag[i] = 1; flag[j] = 1; } } } } for(int i = 0; i < n; i++) {//遍历数组,找到元素的值为0的,将下标给A数组,说明就是这个 if(flag[i] == 0) return A[i]; } } };