【OJ】Chapter 01 - （旋转数组的最小数字、数字在升序数组中出现的次数、错误的集合） 超详细讲解

int minNumberInRotateArray(int* nums, int numsLen )
{
    int i = 0;
    int min = nums[0];
    for(i = 1; i<numsLen; i++)
    {
        if(min>nums[i])
        {
            min = nums[i];
        }
    }
    
    return min;
}

int minNumberInRotateArray(int* nums, int numsLen )
{
    int left = 0;
    int right = numsLen - 1;
    
    while(right > left)
    {
        int mid = left + (right - left)/2;
        if(nums[mid]>nums[right])
        {
            //说明最小值一定在中轴的右边
            left = mid + 1;
        }
        else if(nums[mid] == nums[right])
        {
            right--;
        }
        else
        {
            right = mid;
        }
    }
    
    return nums[right]; //这里也可以写成nums[left],因为最后的循环的退出条件就是left == right
}

int GetNumberOfK(int* nums, int numsLen, int k )
{
    int count = 0;//统计该数字在数组中出现的次数
    for(int i = 0; i<numsLen; i++)
    {
        if(nums[i] == k)
        {
            count++;
        }
    }
    
    return count;
}

int GetNumberOfK(int* nums, int numsLen, int k )
{
	int count = 0;
    int right = numsLen - 1;
    int left = 0;
    
    while(left <= right)
    {
        if(k>nums[right])
        {
            //大于该数组最右边的数字(最大的数字)，那就说明要查找的数字不在该数组中
            return 0;
        }
        else if(k == nums[right])
        {
            count++;
            right--;
        }
        else
        {
            int mid = left + (right - left)/2;
            if(k > nums[mid])
            {
                //说明该数字就会在中轴的右边出现
                left = mid + 1;
			}
            else if(k == nums[mid])
            {
                //说明该数字无法确定中轴的左右两边是否会出现，最保险的做法就是缩小右边界的范围继续查找，此时就是right--
                right--;
            }
            else
            {
                //说明该数字就会出现在中轴的左边
                right = mid - 1;
            }
        }
    }
    
    return count;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#include<stdlib.h>
int* findErrorNums(int* nums, int numsSize, int* returnSize) 
{
    int* flag = (int*)calloc(numsSize+1,sizeof(int));//标记数组，与题目的数组进行一个映射关系.从1开始记起
    int* ret = malloc(sizeof(int)*2);
    
    int old_sum = 0;
    int new_sum = 0;
    
   for(int i = 0; i<numsLen; i++)
   {
       if(flag[nums[i]] == 1)//为什么这样写？原因就是，原本数组中每个元素的值都是不一样的
       {
           ret[0] = nums[i];//找到了错误的数据了
           break;
       }
       flag[nums[i]] = 1;
   }
    
    for(int i = 0; i<numsLen; i++)
    {
        old_sum += i + 1;
        new_sum += nums[i];
    }
    
    //为了找到对应正确的数字，我们可以拿未改变过数组的和，减去除了出现问题的那个数字外的每一个元素
    ret[1] = old_sum - (new_sum - ret[0]);
    
    *returnSize = 2;
    
    free(flag);
    return ret;
    

}