leetcode
leetcode 1551 ~ 1600
检查数组是否经排序和轮转得到

检查数组是否经排序和轮转得到

难度:

标签:

题目描述

代码结果

运行时间: 24 ms, 内存: 16.5 MB


/*
题目思路:
1. 使用Java Stream API对数组进行判断。
2. 检查数组中是否存在多于一个的翻转点。
3. 使用stream和filter计算翻转点的数量,如果多于一个则返回false。
*/

import java.util.stream.IntStream;

public class Solution {
    public boolean check(int[] nums) {
        int n = nums.length;
        long count = IntStream.range(0, n)
                               .filter(i -> nums[i] > nums[(i + 1) % n])
                               .count();
        return count <= 1;
    }
}

解释

方法:

这个解法是通过一次扫描数组来检查是否存在一个单一的下降点,这个下降点表明数组从这里开始被轮转。首先遍历数组,找到第一个元素对(nums[i], nums[i-1]),使得nums[i] < nums[i-1],这意味着数组在这里发生了旋转。如果没有发现这样的对,则数组是非递减的,直接返回true。找到旋转点后,检查从旋转点开始到数组结束之间的元素是否保持非递减顺序,如果这些元素依旧非递减并且数组的最后一个元素不大于数组的第一个元素,则返回true;否则返回false。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在算法中,你是如何确定数组中只有一个下降点就能够判断该数组是通过轮转获得的?
在一个被排序后通过轮转得到的数组中,最多只会出现一个下降点。这是因为轮转操作相当于将数组从某一点断开然后将前半部分移至数组尾部。这种操作保证了除了一个潜在的断点外,数组的其余部分保持原有的排序顺序。因此,如果通过扫描发现超过一个下降点,那么数组不可能只通过一次轮转操作从一个排序数组变换而来。
🦆
如果数组中存在重复的最大元素,会对寻找旋转点的逻辑产生什么影响?例如,数组[2,2,3,3,1,2]应该返回什么结果?
如果数组中存在重复的最大元素,可能会在判断是否只有一个下降点时出现误判。例如在数组 [2,2,3,3,1,2] 中,实际上存在两个下降点(一个在3到1之间,另一个在1到2之间),这违反了只有一个下降点的规则。因此,根据当前的算法逻辑,这个数组应该返回 false,因为它不能通过单一的排序和轮转操作得到。
🦆
为什么在找到旋转点后,还需要验证旋转点到数组末尾之间的元素必须保持非递减顺序?
在找到旋转点后,需要验证旋转点到数组末尾之间的元素保持非递减顺序来确保这部分是原数组中的一个连贯部分且未被修改(除了轮转操作外)。如果这部分元素没有保持非递减顺序,那么表示数组可能经过了其他类型的修改,或者旋转操作不仅仅是一个简单的头部到尾部的移动,从而导致不能通过简单的轮转来还原到一个完全排序的数组。
🦆
算法假设了在找到旋转点之后,数组的最后一个元素不大于数组的第一个元素,这个假设在哪些情况下可能不成立?
这个假设在原数组是非严格递增(即允许重复元素)时可能不成立。例如,如果原数组中包含相同的最小和最大元素,且这些元素在轮转后的数组两端出现,那么最后一个元素可能等于甚至大于第一个元素。此外,如果数组中所有元素均相等,那么任何位置的旋转都会使最后一个元素等于第一个元素,这也不符合假设。

相关问题