2024-07-10 寻找峰值

寻找峰值

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] =

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的时间复杂度实现此问题吗？

输入描述：第一行先输入随机整数的个数 N 。 接下来的 N 行每行输入一个整数，代表明明生成的随机数。

输入: [2,4,1,2,7,8,4]
输出: 1  4和8都是峰值元素，返回4的索引1或者8的索引5都可以

解题思路

简单说下思路，题目限定了输入数字的范围，且一个数字只会出现一次，所以我们使用boolean[] arr = new boolean[501]来存储数字是否出现过，然后从前到后输出即可。

亮点

• boolean数组，节省空间开销
• 使用 BufferedReader 读取控制台输入，减少时间开销
• 时间复杂度为 O(n)
• 空间复杂度为 O(n)

实现

public class Test007 {

    /**
     * 给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
     * <a href="https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76?tpId=295&tqId=2227748&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany">...</a>
     * 1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
     * 2.假设 nums[-1] = nums[n] =
     * 3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
     * 4.你可以使用O(logN)的时间复杂度实现此问题吗？
     * <p>
     * 输入：[2,4,1,2,7,8,4]
     * 输出：1
     * 4和8都是峰值元素，返回4的索引1或者8的索引5都可以
     *
     * @param args 输入参数
     */
    public static void main(String[] args) {
        int[] nums = {2, 4, 1, 2, 7, 8, 4};
        System.out.println(new Test007().findPeakElement(nums));
    }

    public int findPeakElement(int[] nums) {
        // write code here
        if (nums.length == 1) {
            return 0;
        }
        int size = nums.length;
        int left = 0;
        int right = size - 1;
        // 2 3 4 5 6
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                // 有可能是个峰值
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
}