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?
這道題首先由于不開辟其他內(nèi)存沟蔑,所以想到了先排序再尋找矫膨,首先是冒泡排序:
class Solution {
public:
int singleNumber(vector<int>& nums) {
int min, max;
//冒泡排序
for(int i = 0; i< nums.size(); i++){
for(int j = i; j<nums.size()-i; j++){
if(nums[j] < nums[i]){
swap(nums[i], nums[j]);
}else if(nums[j] > nums[nums.size()-i-1]){
swap(nums[j], nums[nums.size()-i-1]);
}
}
}
//在已經(jīng)排好序的數(shù)組中進(jìn)行尋找
for(int i = 0; i < nums.size(); i+=2){
if(i == 0&&nums[0]!=nums[1]){
return nums[0];
break;
}else if(i == nums.size()-1&&nums[i]!= nums[i-1]){
return nums[nums.size()-1];
break;
}
else if(nums[i]!=nums[i+1]){
return nums[i];
break;
}
}
return 0;
}
};
但是提交上去之后,超時(shí)了
屏幕快照 2016-09-16 16.34.10.png
說明思路沒有錯(cuò)誤危尿,但是排序太慢了,嘗試掃描一半:
冒泡排序變成:
for(int i = 0; i< (nums.size()-1)/2; i++){//這句話 變成了掃描一般
for(int j = i; j<nums.size()-i; j++){
if(nums[j] < nums[i]){
swap(nums[i], nums[j]);
}else if(nums[j] > nums[nums.size()-i-1]){
swap(nums[j], nums[nums.size()-i-1]);
}
}
}
提交谊娇,依舊會(huì)時(shí)間超限
上網(wǎng)查找排序時(shí)間,總結(jié)來說济欢,一般快排最快小渊,一提交法褥,果然AC酬屉,所以代碼如下
<u>Runtime: 26 ms</u>
class Solution {
public:
vector<int> num;
void quick_sort(int left, int right)
{
if(left<right)
{
int i = left;
int j = right;
int x = num[i];
while(i<j)
{
while(i<j&&num[j]>x)
j--;
if(i<j){
num[i] = num[j];
i++;
}
while(i<j&&num[i]<x)
i++;
if(i<j){
num[j] = num[i];
j--;
}
}
num[i] = x;
quick_sort(left, i-1);
quick_sort(i+1, right);
}
}
int singleNumber(vector<int>& nums) {
num.clear();
num = nums;
quick_sort(0, nums.size()-1);
for(int i = 0; i < num.size(); i+=2){
if(i == 0&&num[0]!=num[1]){
return num[0];
break;
}else if(i == num.size()-1&&num[i]!= num[i-1]){
return num[num.size()-1];
break;
}
else if(num[i]!=num[i+1]){
return num[i];
break;
}
}
return 0;
}
};
根據(jù)網(wǎng)友啟發(fā)呐萨,發(fā)現(xiàn)了一種更簡單的方法酱鸭。
由于n^n=0, 而0^n = n, 所以給定一組數(shù)組
可以將所有數(shù)進(jìn)行一起異或垛吗,最后剩下的那個(gè)數(shù)就是single num,時(shí)間復(fù)雜度為O(N)怯屉,代碼如下
時(shí)間為<u>19ms</u>
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(int i = 0; i<nums.size(); i++){
res = res ^ nums[i];
}
return res;
}
};