【LeetCode】错误的集合&&在排序数组中查找元素的第一个和最后一个位置&&杨氏矩阵&&寻找数组的中心下标&&两个数组的交集

int cmp(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
}
int* findErrorNums(int* nums, int numsSize, int* returnSize) 
{
    qsort(nums,numsSize,sizeof(int),cmp);
    int* ret = (int*)malloc(sizeof(int)*2);
    //ret数组的第一个元素是重复的数字，第二个元素是缺失的数字
    *returnSize = 2;
    int i = 0;
    int prev = 0;//初始化为0可对应缺失的数字是1的情况
    for(i = 0; i < numsSize; i++)
    {
        int cur = nums[i];
        //重复的数字
        if(prev == cur)
        {
            ret[0] = prev;
        }
        //cur - prev == 2 说明cur和prev之间有一个数，这个数就是缺失的数
        else if(cur - prev == 2)
        {
            ret[1] = prev + 1;
        }
        prev = cur;
    }
    //缺失的数字是numsSize
    if(nums[numsSize-1] != numsSize)
    {
        ret[1] = numsSize;
    }
    return ret;
}

int* findErrorNums(int* nums, int numsSize, int* returnSize)
{
    //遍历nums数组，将其中数据对应的位置1， 哪一位如果已经重置过则意味着数据重复了
    int* arr = (int*)calloc(numsSize+1, sizeof(int));//申请numsSize+1个整形空间，并初始化为0
    //申请numsSize+1个整型空间是防止数组越界
    int* ret = (int*)calloc(2, sizeof(int));//申请2个整形空间，并初始化为0
    *returnSize = 2;
    int oddSum = 0;//记录1到numsSize的和
    int curSum = 0;//记录当前数组的和
    int i = 0;
    for(i = 0;i < numsSize; i++)
    {
        if(arr[nums[i]] == 1)//nums[i]这个数字在arr数组的对应位置已经置过1了，则重复
        {
            ret[0] = nums[i];
        }
        arr[nums[i]] = 1;//将标记数组的对应数据位置1
        oddSum += i+1;//1到numsSize的求和
        curSum += nums[i];//当前数组中的数据求和（多了一个重复的，少了一个丢失的）
    }
    ret[1] = oddSum + ret[0] - curSum;//原始总和加上重复的数字再减去当前总和就得到消失的数字
    free(arr);
    return ret;
}

//寻找target的左边界，该函数也可以寻找target的右边界
int binarySearch(int* nums,int numsSize,int target)
{
    int left=0;
    int right=numsSize-1;
    while(left<=right)
    {
        int mid=left+(right-left)/2;
        if(nums[mid]<target)
        {
            left=mid+1;
        }
        else if(nums[mid]>=target)
        {
            right=mid-1;
        }
    }
    return left;
}
int* searchRange(int* nums, int numsSize, int target, int* returnSize)
{
    int first=binarySearch(nums,numsSize,target);//target的左边界
    int last=binarySearch(nums,numsSize,target+1);//target+1的左边界
    int* result=(int*)malloc(sizeof(int)*2);
    *returnSize=2;
    //当first==numsSize时，说明target大于数组的最后一个元素
    //当nums[first]!=target，说明数组中没有target
    if(first==numsSize||nums[first]!=target)
    {
        result[0]=-1;
        result[1]=-1;
        return result;
    }
    else
    {
        result[0]=first;
        result[1]=last-1;//last-1为target1的右边界
        return result;
    }
}

bool searchMatrix(int** matrix, int matrixSize, int matrixColSize, int target)
{
    int row = 0;
    int col = matrixColSize - 1;
    while((row < matrixSize) && (col >= 0))//防止数组越界
    {
        int num = matrix[row][col];//num初始化为右上角的数字
        if(num > target)//如果num大于target，那么num下面的数字都大于target，所以col减减
        {
            col--;
        }
        else if(num < target)//如果num小于target，那么num左边的数字都小于target，所以row加加
        {
            row++;
        }
        else
        {
            return true;
        }
    }
    //循环结束，说明数组中没有target，返回
    return false;
}

int pivotIndex(int* nums, int numsSize)
{
   int sum=0;
   int i=0;
   for(i=0;i<numsSize;i++)
   {
       sum+=nums[i];
   }
   int sum1=0;//左边的和
   int sum2=0;//右边的和
   for(i=0;i<numsSize;i++)
   {
       //nums[i]为中间的数，左和和右和同时加上不影响结果
       sum1+=nums[i];
       sum2=sum-sum1+nums[i];
       if(sum1==sum2)
       {
           return i;
       }
   }
   return -1;
}

int cmp(const void* a, const void* b)
{
    return *(int*)a - *(int*)b;
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
    //先排序
    qsort(nums1,nums1Size,sizeof(int),cmp);
    qsort(nums2,nums2Size,sizeof(int),cmp);
    //返回数组的最大长度是nums1Size或者nums2Size
    int max = nums1Size > nums2Size ? nums1Size : nums2Size;
    int* ret = (int*)malloc(sizeof(int)*max);
    //后利用双指针寻找交集
    int index1 = 0;
    int index2 = 0;
    *returnSize = 0;
    while((index1 < nums1Size) && (index2 < nums2Size))
    {
        int num1 = nums1[index1];
        int num2 = nums2[index2];
        if(num1 == num2)
        {
            // !(*returnSize)对应result数组中没有元素
            // result[(*returnSize) - 1] != num1用于去重
            if(!(*returnSize) || (ret[(*returnSize) - 1] != num1))
            {
                ret[(*returnSize)++] = num1;
            }
            index1++;
            index2++;
        }
        else if(num1 > num2)
        {
            index2++;
        }
        else
        {
            index1++;
        }
    }
    return ret;
}