峰与谷

难度:

标签:

题目描述

In an array of integers, a "peak" is an element which is greater than or equal to the adjacent integers and a "valley" is an element which is less than or equal to the adjacent integers. For example, in the array {5, 8, 4, 2, 3, 4, 6}, {8, 6} are peaks and {5, 2} are valleys. Given an array of integers, sort the array into an alternating sequence of peaks and valleys.

Example:

Input: [5, 3, 1, 2, 3]
Output: [5, 1, 3, 2, 3]

Note:

nums.length <= 10000

代码结果

运行时间: 27 ms, 内存: 16.8 MB

// 思路：
// 使用流操作先将数组排序，然后根据奇偶索引分别填充峰和谷的位置。
// 将排序后的数组的较大一半放在偶数索引位置，较小一半放在奇数索引位置。

import java.util.Arrays;

public class Solution {
    public void wiggleSort(int[] nums) {
        int[] sorted = Arrays.stream(nums).sorted().toArray();
        int n = nums.length;
        for (int i = 1; i < n; i += 2) {
            nums[i] = sorted[--n];
        }
        for (int i = 0; i < n; i += 2) {
            nums[i] = sorted[--n];
        }
    }
}

解释

方法:

此题解的思路是遍历数组，确保偶数索引的元素是谷，奇数索引的元素是峰。具体来说，当遍历到偶数索引i时，如果当前元素nums[i]大于前一个元素nums[i-1]，则交换这两个元素；当遍历到奇数索引i时，如果当前元素nums[i]小于前一个元素nums[i-1]，则交换这两个元素。这样，通过一次遍历，就能够保证数组按照峰与谷的交替顺序排列。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在此算法中，为什么选择从索引1开始遍历，而不是从索引0开始？

▷

在此算法中，从索引1开始遍历是因为我们需要比较当前元素（nums[i]）与其前一个元素（nums[i-1]）并根据条件可能进行交换。如果从索引0开始，那么nums[i-1]将是nums[-1]，即数组的最后一个元素，这在逻辑上不符合我们交替设置峰和谷的初衷，因为数组的开始没有前一个元素可以比较。因此，从索引1开始可以确保每个元素都有一个前一个元素可以进行比较和可能的交换。

🦆

对于数组长度为奇数和偶数的情况，此算法的处理逻辑是否有所不同，特别是在处理最后一个元素时？

▷

在处理长度为奇数和偶数的数组时，此算法的基本逻辑是相同的，即都是尝试使偶数位置是谷，奇数位置是峰。不过，对于数组的最后一个元素，如果数组长度为奇数，则最后一个元素位于偶数位置（从0开始计数），这时应确保它是谷；如果数组长度为偶数，则最后一个元素位于奇数位置，应确保它是峰。因此，数组长度的奇偶性会影响最后一个元素的处理，但整体算法逻辑保持一致。

🦆

算法中的条件判断`if i%2==0`和`else`部分，是否能确保在所有情况下都正确地交替峰和谷？

▷

该算法通过条件判断`if i%2==0`和`else`确保理想情况下每个偶数索引位置的元素是谷，每个奇数索引位置的元素是峰。然而，这种方法可能不总是能够在所有情况下完美地交替峰和谷。特别是在存在重复元素或特定的顺序排列时，单次遍历可能无法完全确保每个偶数位置都小于相邻的奇数位置元素，反之亦然。在某些情况下，可能需要额外的调整或多次遍历以完全达到峰谷交替的效果。

峰与谷

题目描述

代码结果

解释

代码细节讲解

相关问题