本次的题目难度适中,更重要的是积累题目所带给我们的思路。
题目链接:旋转数组的最小数字(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)。最后求该旋转数组的最小值。
很多人一开是就会想到暴力法,就是遍历一遍数组就能够找到该数组中的最小值了。
代码如下:
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)。不难想到,这道题用二分法符合题意。
那具体的操作步骤是怎样的呢? 旋转数组无非就分三种情况:
这时,我们就得用到,原数组是非降序数组了。
想一下,我们以旋转数组的最右边数字为标准,用中轴的数字与其比较,肯定是会出现三种情况:
代码如下:
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
}
题目链接:数字在升序数组中出现的次数(JZ53) 题目描述:
给定一个长度为 n 的非降序数组和一个非负数整数 k ,要求统计 k 在数组中出现的次数
数据范围:0≤n≤1000,0≤k≤100,数组中每个元素的值满足 0≤val≤100 要求:空间复杂度 O(1),时间复杂度 O(logn)
这道题的思路跟上面那道题的思路类似。
为什么会这样说呢? 这是一个升序的数组,如果我们想要找到该数字在升序数组中出现的次数,如果我们知道了中轴的数字与要查找的数字之间的大小关系时,我们就可以这样缩小要搜索的范围。
遍历一遍数组的元素,统计该数字出现的次数。
代码如下:
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;
}
题目链接:645. 错误的集合
题目描述:
集合 s
包含从 1
到 n
的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums
代表了集合 S
发生错误后的结果。
请你找出重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。
这道题的思路比较好用,值得学习。
我们现在来分析一下题目:题目给了我们一个有序的数组,数字范围是1~n。但是现在,这个数组的元素中有两个的值是一样的,现在你要找到它,并把它修改正确的结果和找到那个错误的数字用一个数组返回。
仔细想一下,如果我们给数组中每个不同的值都进行一个标记的话。假设前一个数字已经被标记了,后面一个数字的值跟前一个数字一样,此时我们就会发现该数子就是我们要找的。
/**
* 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;
}
如果觉得本文写的还不错的话,麻烦给偶点个赞吧!!!