旋转数组最小数字、数字在升序数组中出现的次数

---

前言

记录几道巧妙的算法题

---

旋转数组最小数字

题目：

题目链接
**法一：**首先这道题，我们第一次想到的想法，就是暴力求解，遍历数组寻找最小值
时间复杂度：O（N）
空间复杂度：O（1）
我们看一下代码实现：

int minArray(int* numbers, int numbersSize){
       int min=numbers[0];
       for(int i=1;i<numbersSize;i++)
       {
            if(numbers[i]<min)
            min=numbers[i];
       }
       return min;
}

1
2
3
4
5
6
7
8
9
10

感觉还可以；
但是我们做算法题不因满足于此；
法二：
从题目中，我们可以发现一个十分重要的信息，那就是数组是有序，有了有序这个条件，我们相对起来就比较好操作了；首先我们可以这样想：
这不是左旋吗？
我们可以利用二分法来解决这道题，通过中间值与右端点值（为什么是右端点，我们后面解释）作比较，来确定最小值在那个区间，从而在重新在这个区间里面去寻早最小值
1、nums[mid]
2、nums[mid]>nums[right]的情况（旋的比较少的情况，以中间位置为标准，如果最小值在中间位置右边）

3、nums[mid]==nums[right]的情况

综上就这三种情况：最终left= =right的位置就是最小值的位置：

时间复杂度：O（log（N））
空间复杂度：O（1）；
代码实现：

int minArray(int* nums, int numbersSize){
     int mid=0;
     int left=0;
     int right=numbersSize-1;
     while(left<right)
     {
         mid=(left+right)/2;
       if(nums[mid]>nums[right])//左旋转的太少了
       {
           left=mid+1;
       }
       else if(nums[mid]<nums[right])//左旋转的太多了
       {
           right=mid;
       }
       else
       {
           right--;
       }

     }
     return nums[left];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

也还可以；
现在我们来解释一下，为什么比较值会选择右端点值，而不是左端点值？
假设我们选择左端点值：
1、旋的太多，那么nums[mid]
2、旋太少，那么nums[mid]>nums[left],最小值在右区间，left=mid+1；

但是如果我们的序列是 1 2 3 4 5 6 7呢？很明显不能成立嘛，自然也就推翻了用左端点值做比较的情况；
但是我们可以考虑一下，如何用该方法寻找最大值？（思路与寻找最小值一样）
寻找最大值代码：

int minNumberInRotateArray(int* arr, int rotateArrayLen) {
    // write code here
    int left = 0;
    int right = rotateArrayLen - 1;
    int mid = 0;
    while (left < right)
    {
        mid = (left + right) / 2;
        if (arr[mid] > arr[left])//旋的太少了
        {

            left = mid;

        }
        else if (arr[mid] < arr[left])//旋转的太多了
        {

            right = mid-1;
        }
        else
        {
            left++;
        }
    }
    return arr[left];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

数字在升序数组中出现的次数

题目：

题目链接
法一：我们最容易想到的就是暴力破解了，当然暴力破解也是最简单的方法；
时间复杂度：O（N）
空间复杂度：O（1）
代码实现：

int GetNumberOfK(int* nums, int numsSize, int k ) {
    // write code here
    int count=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]==k)
            count++;
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10

法二：暴力解法虽好，但是比较耗时间，我们希望有一个更优的算法来取代暴力破解，
这不是一个有序数组嘛，然后又是让我们找值，在一个有序数组里面找值，这不就很符合二分法的目标吗？只不过普通二分法只能找一处，这道题要求我们找多次嘛，那我们一次一次的找，不就成了多次查找了吗？
对于这种算法，我们可以采取分治的算法；

同理对于有区间也是如此！！！
那如果nums[mid]==k怎么办，嘿！真是太好了，我们找到就是它，他既然出现了，我们就记录一下呗！但是我们无法保证左区间和右区间，是否存在k，于是我们就需要对左右两个区间都进行搜做了：

时间复杂度：O（log N）
空间复杂度：O（1）
代码实现：

 void Dichotomy_check(int*const nums,int*const count,const int key,int left,int right)
 {
     if(left>right)
         return;
     int mid=(left+right)/2;
     if(nums[mid]>key)
     {
         right=mid-1;
         Dichotomy_check(nums,count,key,left,right);//去新区间搜索
     }
     else if(nums[mid]<key)
     {
         left=mid+1;
         Dichotomy_check(nums,count,key,left,right);//去新区间搜索
     }
     else
     {
         (*count)++;
         Dichotomy_check(nums,count,key,left,mid-1);//去左区搜索
         Dichotomy_check(nums,count,key,mid+1,right);//去右区间搜索
     }
         
 }
int GetNumberOfK(int* nums, int numsSize, int k ) {
    // write code here
    int *count=(int*)calloc(1,sizeof(int));//记录次数
    int left=0;
    int right=numsSize-1;
     Dichotomy_check(nums,count,k,left,right);
    int tmp_count=*count;
    free(count);
    count=NULL;
    return tmp_count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34