检查数组是否经排序和轮转得到
难度:
标签:
题目描述
代码结果
运行时间: 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]应该返回什么结果?
▷🦆
为什么在找到旋转点后,还需要验证旋转点到数组末尾之间的元素必须保持非递减顺序?
▷🦆
算法假设了在找到旋转点之后,数组的最后一个元素不大于数组的第一个元素,这个假设在哪些情况下可能不成立?
▷