[牛客网--左老师]局部最小值位置

以你之姓@ 2022-08-10 08:38 129阅读 0赞

定义局部最小的概念。arr长度为1时，arr\[0\]是局部最小。arr的长度为N(N>1)时，如果arr\[0\]<arr\[1\]，那么arr\[0\]是局部最小；如果arr\[N-1\]<arr\[N-2\]，那么arr\[N-1\]是局部最小；如果0<i<N-1，既有arr\[i\]<arr\[i-1\]又有arr\[i\]<arr\[i+1\]，那么arr\[i\]是局部最小。 给定无序数组arr，已知arr中任意两个相邻的数都不相等，写一个函数，只需返回arr中任意一个局部最小出现的位置即可。

代码例程：时间复杂度为O(logN)

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution {
    public:
        int getLessIndex(vector<int> arr) {
            /* 判断数组是否合法 */
            if(arr.empty())
            {
                return -1;
            }
    
            int len = arr.size();
    
    
            /* arr[0],arr[len-1]是否是局部最小 */
            if(len == 1 || arr[1] > arr[0])
            {
                return 0;
            }
    
            if(arr[len-1] < arr[len-2])
            {
                return len-1;
            }
    
            int left = 1;
            int right = len - 2;
            int mid = 0;
    
            while(left < right)
            {
                mid = (left + right) / 2;
    
                if (arr[mid] > arr[mid-1])
                {
                    right = mid-1;
                }
                else if (arr[mid] > arr[mid+1])
                {
                    left = mid + 1;
                }
                else
                {
                    return mid;
                }
            }
    
            return left;
    
        }
    };
    
    
    int main( void )
    {
        int a[7] = {6,5,2,4,5};
        Solution mg;
        vector<int> v(a,a+4);
    
        cout << mg.getLessIndex(v) << endl;
    
        return 0;
    }