[leetcode每日一题] 540. 有序数组中的单一元素

yyyyye

难度分析：

难度：较易
时间复杂度： $O(\log{n})$
空间复杂度：$O(1)$

解题思路：

二分查找：方法应该比较容易想到二分，关键在于check函数的设置。不难发现，当唯一数在mid前后，对每对相同数所在位置的奇偶性有影响。

代码：

class Solution {
    bool check(int mid, vector<int>& nums)
    {
        return nums[mid] == nums[mid + (mid & 1 ? -1 : 1)];
    }

public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size(), l = 0, r = n - 1, mid = l + ((r - l) >> 1);
        while(l < r)
        {
            mid = l + ((r - l) >> 1);
            if(mid != 0 && mid != n - 1 && nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1])
            {
                return nums[mid];
            }
            else if(check(mid, nums))
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }
        return nums[l];
    }
};

If_you_love

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        unordered_map <int,int> res;
        for (int i:nums)
        {
            if(res[i])
            {
                res.erase(i);
            }
            else 
            {
                res[i]=1;
            }
        }
        int t;
        for (auto p=res.begin();p!=res.end();p++)
        {
            t=p->first;
        }
        return t;
    }
};

不太满足条件，时间复杂度：$O(N)$；空间复杂度：$O(N)$

yyyyye

If_you_love 你这时间复杂度可能得$O(n\log{n})$，stl库函数的复杂度也得算进去，erase还需要$\log{n}$。而且你要遍历的话普通数组比map快多了，能用数组映射没必要非用map呀。

Zero_canyon

暴力遍历，时间复杂度:O(n)；空间复杂度:O(1);

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int len = nums.size();
        for(int i = 0;i < len-2;i+=2)
        {
            if(nums[i] != nums[i+1])
            {
                return nums[i];
            }
        }
        return nums[len-1];
    }
};

小优化了一下

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int len = nums.size();
        if(len==1)
        return nums[0];
        for(int i = 0;i < len/2;i+=2)
        {
            if(nums[i] != nums[i+1])
            {
                return nums[i];
            }
            else if(nums[len-1-i] != nums[len-i-2])
                return nums[len-1-i];
        }
        return nums[len/2];
    }
};

ssssshi

建立数组，有就删没有就插，最后只剩单身汉

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        vector<int> arr;
        for(int i = 0; i < nums.size(); i++) {
            auto it = find(arr.begin(), arr.end(), nums[i]);
            if(it == arr.end()) {
                arr.push_back(nums[i]);
            } else {
                arr.erase(it);
            }
        }
        return arr.at(0);
    }
};

xujingyuan

用一个计数数组，找出数量为1的数字，输出结束。复杂度不满足条件，可以用二分（我不会）。

int singleNonDuplicate(int* nums, int numsSize) {
    int a[100009]={0};
    for(int i=0;i<numsSize;i++)
    {
        a[nums[i]]++;
    }
    int j;
    for(j=0;j<100009;j++)
    {
        if(a[j]==1)
        {
            break;
        }
    }
    return j;
}

ygxdsh

xujingyuan 加训！

冰魄

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n=nums.size();int k=0;
        for(int i=0;i<n;i++)
        {
            k=k^nums[i];
        }
        return k;
    }
};

wszyh

求数组长度，如果是1直接输出，遍历整个数组找单独的那个，如果是最后一个加2时会直接跳出循环这时直接返回最后一个值

public:
    int singleNonDuplicate(vector<int>& nums) {
        int n=nums.size();
        if(n==1)return nums[0];
        for(int i=0;i<n-1;){
            if(nums[i]!=nums[i+1]){
                return nums[i];
            }
            i+=2;
        }
        return nums[n-1];
    }
};

ygxdsh

要求：时间复杂度O(logn)，加上有序数组直接锁定二分。

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l=0,r=(nums.size()-1)/2;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(nums[mid*2]==nums[mid*2+1]) l=mid+1;
            else r=mid;
        }
        return nums[l*2];
    }
};

先找一下规律，答案的下标一定是偶数
然后在看看二分判断条件怎么写？
仔细思考一下，有了！
如果答案在mid右边，那么必然导致mid与mid左边的数不相等。（此处mid是指nums[mid2]）
因为nums[mid2]的下标必然是偶数，如果前面没有单独的一个数（也就是要找的答案）
就会有nums[0]==nums[1],nums[1*2]==nums[1*2+1],......,nums[mid*2]==nums[mid*2+1];

当然，用另一种整数二分模板也可以解决

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l=0,r=(nums.size()-1)/2;
        while(l<r)
        {
            int mid=(l+r+1)/2;
            if(nums[mid*2-1]==nums[mid*2]) l=mid;
            else r=mid-1;
        }
        return nums[l*2];
    }
};

原理类似，就不过多赘述了

WaTEr

二分思路：
我们可以从题目得知，拿到的数组中只有一个元素会出现一次，其余的都是两次出现，那么我们可以确定这个数组的长度一定是奇数。
此时我们通过二分找到这个数组的中项，它可能是两个相同元素的第一项或是第二项，我们就需要用一下两行代码来判断
if (mid + 1 < nums.size()&&nums[mid] == nums[mid + 1])
else if (mid - 1 >= 0 &&nums[mid] == nums[mid - 1])
（前面的mid+1和mid-1是为了防止溢出）
然后我们将这两个相同元素看作为一个元素，去找这个元素左右两边的数组哪一个是奇数长度，就能知道单独出现的元素在哪一边，
就用这两堆代码：

 int rr = r - mid - 1;
                if (rr % 2 == 1) {
                    l = mid + 2;
                } else {
                    r = mid - 1;
                }

int rr = r - mid;
                if (rr % 2 == 1) {
                    l = mid + 1;
                } else {
                    r = mid - 2;
                }
            }

以此类推，我们就能找到单独出现的元素了
当然，会有直接在某一次找中项中找到单独出现的元素的情况，那么就需要加上break了
附上完整代码：

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int mid = 0, l = 0, r = nums.size() - 1;

        while (r >= l) {
            mid = (l + r + 1) / 2;
             if (mid + 1 < nums.size()&&nums[mid] == nums[mid + 1]) {
                int rr = r - mid - 1;
                if (rr % 2 == 1) {
                    l = mid + 2;
                } else {
                    r = mid - 1;
                }
            } else if (mid - 1 >= 0 &&nums[mid] == nums[mid - 1]) {
                int rr = r - mid;
                if (rr % 2 == 1) {
                    l = mid + 1;
                } else {
                    r = mid - 2;
                }
            } 
            else break;          
        }
        return nums[mid];
    }
};

Yln_wlp

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int ret = 0;
        for(int i = 0;i < nums.size();i++){
            ret^=nums[i];
        }
        return ret;
    }
};

额

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l<r){
            int mid = l + (r - l)/2;
            if(mid%2==0){
                if(nums[mid]==nums[mid+1]) l = mid + 1;
                else r = mid;
            }
            else{
                if(nums[mid]==nums[mid-1]) l = mid + 1;
                else r = mid;
            }
        }
        return nums[l];
    }
};

利用奇偶性