题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。

输入描述

题目保证输入的数组中只有两个数字出现一次
数据范围：
  对于%50的数据,size<=10^4
  对于%75的数据,size<=10^5
  对于%100的数据,size<=2*10^5

示例

输入

1,2,2,3,3,4,5,5,6,6,7,7,7

输出

1,4

思路

因为这一题的vector的size很大，以至于直接遍历寻找逆序对会超时，为了避免这种情况，我使用快速排序算法。快速排序算法，主要流程
第一步:我们将数组num[0]设置为哨兵x，然后从s=0，e=num.length()-1,如果s==e，跳出快排;
第二步:从e开始从后往前找到一个小于x的数num[e]，将num[e]和num[s]交换
第三步:从s开始从前往后找到一个大于x的数num[s]，将num[s]和num[e]交换
第四步:重复第二、三步，直到s==e，此时num被划分成两部分，num[0,s-1]都小于num[s]，num[s+1,num.length() - 1]都大于num[s]，但序列内不一定有序，故我们应该对num[0,s-1],num[s+1,num.length() - 1]递归的进行快排.

代码

#include "iostream"
#include "string"
#include "vector"
using namespace 

void Func(vector<int> &data, int l, int r)
{
    if (l >= r)
    {
        return;
    }
    int x = data[l], s = l, e = r, tmp;
    while (s != e)
    {
        while (s != e)
        {
            if (data[e] < x)
            {
                tmp = data[e];
                data[e] = data[s];
                data[s] = tmp;
                break;
            }
            e--;
        }
        while (s != e)
        {
            if (data[s] > x)
            {
                tmp = data[e];
                data[e] = data[s];
                data[s] = tmp;
                break;
            }
            s++;
        }
    }
    Func(data, l, s - 1);
    Func(data, s + 1, r);
}

void FindNumsAppearOnce(vector<int> data, int *num1, int *num2)
{
    Func(data, 0, data.size() - 1);
    bool find = false;
    for (int i = 0; i < data.size(); i++)
    {
        if (i == 0)
        {
            if (data[i] == data[i + 1])
            {
                continue;
            }
        }
        else if(i == data.size() - 1)
        {
            if (data[i] == data[i - 1])
            {
                continue;
            }
        }
        else if (data[i] == data[i + 1] || data[i] == data[i - 1])
        {
            continue;
        }

        if (!find)
        {
            *num1 = data[i];
            find = true;
        }
        else
        {
            *num2 = data[i];
            break;
        }
    }
    return;
}