C#LeetCode刷题之#852-山脉数组的峰顶索引(Peak Index in a Mountain Array)

C#LeetCode刷题之#852-山脉数组的峰顶索引(Peak Index in a Mountain Array)

问题

我们把符合下列属性的数组 A 称作山脉:

  • A.length >= 3
  • 存在 0 < i < A.length – 1 使得A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length – 1]

给定一个确定为山脉的数组,返回任何满足 A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length – 1] 的 i 的值。

输入:[0,1,0]

输出:1

输入:[0,2,1,0]

输出:1

提示:

  • 3 <= A.length <= 10000
  • 0 <= A[i] <= 10^6
  • A 是如上定义的山脉

Let’s call an array A a mountain if the following properties hold:

  • A.length >= 3
  • There exists some 0 < i < A.length – 1 such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length – 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length – 1].

Input: [0,1,0]

Output: 1

Input: [0,2,1,0]

Output: 1

Note:

  • 3 <= A.length <= 10000
  • 0 <= A[i] <= 10^6
  • A is a mountain, as defined above.

示例

public class Program {

    public static void Main(string[] args) {
        var A = new int[] { 24, 69, 100, 99, 79, 78, 67, 36, 26, 19 };

        var res = PeakIndexInMountainArray(A);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static int PeakIndexInMountainArray(int[] A) {
        //二分法
        var low = 1;
        var high = A.Length - 2;
        var mid = 0;
        while(low <= high) {
            mid = low + (high - low) / 2;
            var top = Position(A, mid);
            if(top == 1) {
                high = mid - 1;
            } else if(top == -1) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    private static int Position(int[] A, int index) {
        //-1,index在峰顶左边
        //1,index在峰顶右边
        //0,index是峰顶
        if(A[index] > A[index - 1] && A[index + 1] > A[index]) return -1;
        if(A[index + 1] < A[index] && A[index] < A[index - 1]) return 1;
        return 0;
    }

}

以上给出1种算法实现,以下是这个案例的输出结果:

2

分析:

显而易见,以上算法的时间复杂度为: O(logn) 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4003

发表评论

登录后才能评论