首页 > 其他 > 详细

LeetCode Solution-136

时间:2020-02-05 23:47:43      阅读:69      评论:0      收藏:0      [点我收藏+]
136. Single Number

Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

思路
首先将数组排序,然后判断每个数与前后是否都不相等,如果都不相等则返回。注意首尾的值单独拿出来比较。

Solution:

int singleNumber(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    sort(nums.begin(), nums.end());
    
    if (nums[0] != nums[1]) return nums[0];
    for (int i = 1; i < n-2; i++) {
        if (nums[i] != nums[i-1] && nums[i] != nums[i+1])
            return nums[i];
    }
    return nums[n-1];
}

性能
Runtime: 24 ms??Memory Usage: 9.9 MB

LeetCode Solution-136

原文:https://www.cnblogs.com/dysjtu1995/p/12267162.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!