【OJ】Chapter 01

admin管理员组

文章数量:1794759

【OJ】Chapter 01

前言

本次的题目难度适中，更重要的是积累题目所带给我们的思路。

题目1：旋转数组的最小数字（JZ11)

题目链接：旋转数组的最小数字（JZ11) 题目描述： 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000

要求：空间复杂度：O(1)，时间复杂度：O(logn)

我们不妨先整理题目的有效条件：题目给的数组是非降序的，并且旋转数组就是在这个数组的基础上进行变形的。 再看题目的条件，要求时间复杂度为O(logn)，空间为O(1)。最后求该旋转数组的最小值。

方法1（暴力法）

很多人一开是就会想到暴力法，就是遍历一遍数组就能够找到该数组中的最小值了。

代码如下：

代码语言：javascript代码运行次数：0运行复制

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;
}

这种方法虽然能够解决问题，但是这并不符合题目的要求。仔细看看该算法的时间复杂度为O(n)。与题目的O(logn)不符。

那还有什么方法吗？

别忘了，我们还有一个条件，该旋转数组之前是一个非降序的数组。而且要求我们的时间复杂度为O(logn)。不难想到，这道题用二分法符合题意。

方法2（二分法）

那具体的操作步骤是怎样的呢？ 旋转数组无非就分三种情况：

情况

这时，我们就得用到，原数组是非降序数组了。

想一下，我们以旋转数组的最右边数字为标准，用中轴的数字与其比较，肯定是会出现三种情况：

1. 如果中轴的数字大于最右边的数字，说明最小值一定在中轴的右边。 有的人可能会说这是为什么？这就是非降序数组带来的效果。仔细想一下，非降序数组旋转之后，数组就分为了两部分的非降序数组了，至于以数组的那个位置作为分界，这就需要我们进行判断了。中轴的数字大于最右边的数字，说明了一定是在中轴数字之内的数。
2. 如果中轴的数字等于最右边的数字，说明了此时我们就得缩小查找的范围。(将右边界缩小一个单位) 有的人可能会问，为什么要缩小范围？你可以想一下，中轴的数字等于最右边的数字，我们就得不断缩小右边界范围，直至出现情况1和情况3.如果没有出现就说明，该值就为最小值。
3. 如果中轴的数字小于最右边的数字，说明最小值可能是它，也可能是出现在中轴的左边。

代码如下：

代码语言：javascript代码运行次数：0运行复制

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
}

---

题目2:数字在升序数组中出现的次数（JZ53）

题目链接：数字在升序数组中出现的次数（JZ53） 题目描述：

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围：0≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100 要求：空间复杂度 O(1)，时间复杂度 O(logn)

示例

这道题的思路跟上面那道题的思路类似。

为什么会这样说呢？ 这是一个升序的数组，如果我们想要找到该数字在升序数组中出现的次数，如果我们知道了中轴的数字与要查找的数字之间的大小关系时，我们就可以这样缩小要搜索的范围。

方法1（暴力法）

遍历一遍数组的元素，统计该数字出现的次数。

代码如下：

代码语言：javascript代码运行次数：0运行复制

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;
}

方法2（二分法）

依然沿用上面一道题目的思想，不过这里我们还得添加一些别的东西。

仔细思考一下，我们要查找的数字，

1. 如果直接大于该数组最右边的数字(最大的数字)，那就说明要查找的数字不在该数组中；
2. 如果等于该数组的最右边的数字时，我们先给计数器变量(count)加1，之后再将搜索范围缩小一个单位； 原因是：可能会出现多个相同数字出现的情况。那有的人就会说，时间复杂度会不会变高啊？我想说的是不会的。
3. 如果小于该数组中的最右边的数字时，这就要拿查找的数字与该数组的中轴数字进行比较：
   • 如果大于该中轴数字，说明该数字就会在中轴的右边出现，此时就left=mid+1;
   • 如果等于该中轴数字，说明该数字无法确定中轴的左右两边是否会出现，最保险的做法就是缩小右边界的范围继续查找，此时就是right - -；
   • 如果小于该中轴数字，说明该数字就会出现在中轴的左边，此时就是，right = mid - 1;

代码如下：

代码语言：javascript代码运行次数：0运行复制

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;
}

题目3：错误的集合

题目链接：645. 错误的集合

题目描述：

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例

这道题的思路比较好用，值得学习。

我们现在来分析一下题目：题目给了我们一个有序的数组，数字范围是1~n。但是现在，这个数组的元素中有两个的值是一样的，现在你要找到它，并把它修改正确的结果和找到那个错误的数字用一个数组返回。

仔细想一下，如果我们给数组中每个不同的值都进行一个标记的话。假设前一个数字已经被标记了，后面一个数字的值跟前一个数字一样，此时我们就会发现该数子就是我们要找的。

方法（标记法）

代码语言：javascript代码运行次数：0运行复制

/**
 * 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;
    

}

如果觉得本文写的还不错的话，麻烦给偶点个赞吧！！！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-16，如有侵权请联系 cloudcommunity@tencent 删除前往查看int集合数据数组统计

本文标签： OJChapter 01