C++刷剑指offer（面试题56 - I. 数组中数字出现的次数）【数据结构】

糖逗

题目描述：

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

 

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
 

限制：

2 <= nums <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

 

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
 

限制：

2 <= nums <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <stack>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;


vector<int> solution(vector<int>& input){
        vector<int> res;
        sort(input.begin(), input.end());
        stack<int> temp; 
        for(int i = 0; i < input.size(); i++){
                if(temp.empty() || temp.top() != input[i]){
                        temp.push(input[i]);
                        continue;
                }
                if(temp.top() == input[i]){
                        temp.pop();
                        continue;
                }
        }
        int len = temp.size();
        for(int j = 0; j < len; j++){
                res.push_back(temp.top());
                temp.pop();
                
        }
        return res;
}

int main(void){
        vector<int> input;
        int number;
        while(cin >> number){
                input.push_back(number);
        }
        vector<int> res = solution(input);
        for(int i = 0; i < res.size(); i++){
                cout << res[i] << " ";
        } 
        cout << endl;
        return 0;
}

注意事项：
1.暂无。