// language c
// 剑指56-I
// https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
// 通过了，但是肯定能优化，需要用到亦或，不太懂
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

// 排序是nlogn不太符合，但是好先试试吧
int* singleNumbers(int* nums, int numsSize, int* returnSize){
    returnSize[0] = 2;
    int partition(int arr[],int low, int high){
        int pivot = arr[low];
        while (low <high){
            while(low <high && arr[high] >=pivot)   high--;
            arr[low] = arr[high];
            while(low <high && arr[low] <= pivot)   low++;
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }
    void quick_sort_inside(int arr[], int start, int end){
        int pivot = partition(arr,start,end);
        if (start < pivot-1) quick_sort_inside(arr, start, pivot-1);
        if (end > pivot+1) quick_sort_inside(arr, pivot+1, end);
    }
    quick_sort_inside(nums,0,numsSize-1);
    int a;
    int b;
    bool a_found =false,done = false;

    void fill(int m){
        if(a_found){
            b = m;
            done = true;
        }else{
            a = m;
            a_found = true;
        }

    if(nums[0]<nums[1])
        fill(nums[0]);
    if(nums[numsSize-1]>nums[numsSize-2]){
        fill(nums[numsSize-1])
        if(done){
            nums[0] = a;
            nums[1] = b;
            return nums;
        }
    }
    for(int i=1; i<numsSize-1;i++){
        if((nums[i]>nums[i-1])&&(nums[i]<nums[i+1])){
            fill(nums[i])
            if(done){
                nums[0] = a;
                nums[1] = b;
                return nums;
            }
        }
    }
    return nums;
}