C语言每日一练-----Day(4)

本专栏为c语言练习专栏，适合刚刚学完c语言的初学者。本专栏每天会不定时更新，通过每天练习，进一步对c语言的重难点知识进行更深入的学习。

今日练习题关键字：记负均正    旋转数组的最小数字    二分查找

题目一：

题目描述：

题目来源：记负均正

首先输入要输入的整数个数n，然后输入n个整数。输出为n个整数中负数的个数，和所有正整数的平均值，结果保留一位小数。

0既不是正整数，也不是负数，不计入计算。如果没有正数，则平均值为0。

数据范围： 1≤n ≤2000 ，输入的整数都满足 ∣val∣≤1000

输入描述：

首先输入一个正整数n，

然后输入n个整数。

输出描述：

输出负数的个数，和所有正整数的平均值。

解题思路：

1.边输入边统计负数个数

2.边输入边统计正整数个数，注意0既不是正整数，也不是负整数，否则求平均会出问题

3.求平均时特殊处理除数为0的情况

代码实现：

#include<stdio.h>
int main() 
{
    int cnt;
    int num[2000];
    int avr = 0;
    int negtive = 0;
    float sum = 0;
    scanf("%d", &cnt);
    for (int i = 0; i < cnt; i++) 
    {
        scanf("%d", &num[i]);
        if (num[i] < 0) 
        {
            negtive++;
        }
        if (num[i] > 0) 
        {
            avr++;
            sum += num[i];
        }
    }
    //输出负数个数|所有正数平均值，结果保留一位小数
    if (avr == 0) 
    {//考虑除数为0的情况
        printf("%d 0.0\n", negtive);
    }
    else 
    {
        printf("%d %0.1f\n", negtive, sum / avr);
    }
    return 0;
}

结果情况：

符合题目要求，问题解决。

题目二：

题目描述：

题目来源：旋转数组的最小数字

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

解题思路：

这道题目,我们可以采用一个方法:二分查找.

1.为什么想到二分查找？

二分查找的本质的本质是二段性，只要满足二段性的问题都可以使用二分查找求解。

在本题中二分查找的二段性体现在：最小值左边的单调增，最小值右边的单调增。且左边的元素都大于右边的元素。

2.如何解决分段单调的问题？

很简单，我们只需要比对arr[mid]与arr[0]和arr[numsSize - 1]的大小关系就可以：

1.arr[mid] > arr[0],说明mid此时落在最小值左边

2.arr[mid] < arr[numsSize - 1]，说明此时mid落在最小值的右边。

根据这一特性我们利用左闭右开型的二分查找就可以压缩出最小值所在的地方。

到此我们可以写下这样的一段代码

int minNumberInRotateArray(int* arr, int arrSize) 
{
    int left = 0;
    int right = arrSize - 1;
    while(left < right)
    {
        int mid = (left + right) / 2;
        if(arr[mid] >= arr[0])
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return arr[left];
}

3.上面的写法发生错误,为什么呢？

因为题目只是说到非降序，所以不能排除出现重复的情况：

4.如何解决重复的问题?

我们重点对数据的右边进行去重

1.如果发生arr[mid] < arr[right],则和上面一样使得right = mid。

2.如果发生arr[mid] > arr[right],则和上面一样使得left = mid + 1。

3.如果发生arr[mid] == arr[right],则说明发生重复，对于重复我们将right–，因为既然有重复，那删掉其中一个可以保证至少还有1个。

这样不断删之后可以排除重复的影响，最终的代码如下:

代码实现：

int minNumberInRotateArray(int* arr, int arrSize) 
{
    int left = 0;
    int right = arrSize - 1;
    while(left < right)
    {
        int mid = (left + right) / 2;
        if(arr[mid] < arr[right])
            right = mid;
        else if(arr[mid] > arr[right])
            left = mid + 1;
        else
            right -= 1;
    }
    return arr[left];
}

结果情况：

调整过后的代码符合题目要求,题目得到解决.

总结：

今天的两道编程题整体来说难度不大。只不过有个新颖的点在于：第二道题用到了二分查找。通过不断改进我们的思路，一步一步完善，最后将问题解决。

文章到这里就要告一段落了，有更好的想法或问题，欢迎评论区留言。

希望今天的练习能对您有所收获，咱们下期见！