只出现一次的数字 III

问题描述

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]

注意:
结果输出的顺序并不重要,对于上面的例子, [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-number-iii

思路

  • 首先将数组进行排序
  • 遍历一次数组

首尾两个元素进行特判,看头元素是否不等于第二个元素,看尾元素是否不等于倒数第二个元素
对于中间元素,看起是否不等于前一个元素,或者不等于后一个元素

题解

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

标签: none

添加新评论