返回介绍

solution / 2800-2899 / 2855.Minimum Right Shifts to Sort the Array / README_EN

发布于 2024-06-17 01:02:59 字数 4514 浏览 0 评论 0 收藏 0

2855. Minimum Right Shifts to Sort the Array

中文文档

Description

You are given a 0-indexed array nums of length n containing distinct positive integers. Return _the minimum number of right shifts required to sort _nums_ and _-1_ if this is not possible._

A right shift is defined as shifting the element at index i to index (i + 1) % n, for all indices.

 

Example 1:

Input: nums = [3,4,5,1,2]
Output: 2
Explanation: 
After the first right shift, nums = [2,3,4,5,1].
After the second right shift, nums = [1,2,3,4,5].
Now nums is sorted; therefore the answer is 2.

Example 2:

Input: nums = [1,3,5]
Output: 0
Explanation: nums is already sorted therefore, the answer is 0.

Example 3:

Input: nums = [2,1,4]
Output: -1
Explanation: It's impossible to sort the array using right shifts.

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • nums contains distinct integers.

Solutions

Solution 1: Direct Traversal

First, we use a pointer $i$ to traverse the array $nums$ from left to right, finding a continuous increasing sequence until $i$ reaches the end of the array or $nums[i - 1] > nums[i]$. Next, we use another pointer $k$ to traverse the array $nums$ from $i + 1$, finding a continuous increasing sequence until $k$ reaches the end of the array or $nums[k - 1] > nums[k]$ and $nums[k] > nums[0]$. If $k$ reaches the end of the array, it means the array is already increasing, so we return $n - i$; otherwise, we return $-1$.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $nums$.

class Solution:
  def minimumRightShifts(self, nums: List[int]) -> int:
    n = len(nums)
    i = 1
    while i < n and nums[i - 1] < nums[i]:
      i += 1
    k = i + 1
    while k < n and nums[k - 1] < nums[k] < nums[0]:
      k += 1
    return -1 if k < n else n - i
class Solution {
  public int minimumRightShifts(List<Integer> nums) {
    int n = nums.size();
    int i = 1;
    while (i < n && nums.get(i - 1) < nums.get(i)) {
      ++i;
    }
    int k = i + 1;
    while (k < n && nums.get(k - 1) < nums.get(k) && nums.get(k) < nums.get(0)) {
      ++k;
    }
    return k < n ? -1 : n - i;
  }
}
class Solution {
public:
  int minimumRightShifts(vector<int>& nums) {
    int n = nums.size();
    int i = 1;
    while (i < n && nums[i - 1] < nums[i]) {
      ++i;
    }
    int k = i + 1;
    while (k < n && nums[k - 1] < nums[k] && nums[k] < nums[0]) {
      ++k;
    }
    return k < n ? -1 : n - i;
  }
};
func minimumRightShifts(nums []int) int {
  n := len(nums)
  i := 1
  for i < n && nums[i-1] < nums[i] {
    i++
  }
  k := i + 1
  for k < n && nums[k-1] < nums[k] && nums[k] < nums[0] {
    k++
  }
  if k < n {
    return -1
  }
  return n - i
}
function minimumRightShifts(nums: number[]): number {
  const n = nums.length;
  let i = 1;
  while (i < n && nums[i - 1] < nums[i]) {
    ++i;
  }
  let k = i + 1;
  while (k < n && nums[k - 1] < nums[k] && nums[k] < nums[0]) {
    ++k;
  }
  return k < n ? -1 : n - i;
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文