Question

801. Minimum Swaps To Make Sequences Increasing

中文文档

Description

You are given two integer arrays of the same length nums1 and nums2. In one operation, you are allowed to swap nums1[i] with nums2[i].

• For example, if nums1 = [1,2,3,8], and nums2 = [5,6,7,4], you can swap the element at i = 3 to obtain nums1 = [1,2,3,4] and nums2 = [5,6,7,8].

Return _the minimum number of needed operations to make _nums1_ and _nums2_ strictly increasing_. The test cases are generated so that the given input always makes it possible.

An array arr is strictly increasing if and only if arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1].

 

Example 1:

Input: nums1 = [1,3,5,4], nums2 = [1,2,3,7]
Output: 1
Explanation: 
Swap nums1[3] and nums2[3]. Then the sequences are:
nums1 = [1, 3, 5, 7] and nums2 = [1, 2, 3, 4]
which are both strictly increasing.

Example 2:

Input: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]
Output: 1

 

Constraints:

• 2 <= nums1.length <= 105
• nums2.length == nums1.length
• 0 <= nums1[i], nums2[i] <= 2 * 105

Solutions

Solution 1

class Solution:
  def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
    a, b = 0, 1
    for i in range(1, len(nums1)):
      x, y = a, b
      if nums1[i - 1] >= nums1[i] or nums2[i - 1] >= nums2[i]:
        a, b = y, x + 1
      else:
        b = y + 1
        if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]:
          a, b = min(a, y), min(b, x + 1)
    return min(a, b)

class Solution {
  public int minSwap(int[] nums1, int[] nums2) {
    int a = 0, b = 1;
    for (int i = 1; i < nums1.length; ++i) {
      int x = a, y = b;
      if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) {
        a = y;
        b = x + 1;
      } else {
        b = y + 1;
        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
          a = Math.min(a, y);
          b = Math.min(b, x + 1);
        }
      }
    }
    return Math.min(a, b);
  }
}

class Solution {
public:
  int minSwap(vector<int>& nums1, vector<int>& nums2) {
    int a = 0, b = 1, n = nums1.size();
    for (int i = 1; i < n; ++i) {
      int x = a, y = b;
      if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) {
        a = y, b = x + 1;
      } else {
        b = y + 1;
        if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
          a = min(a, y);
          b = min(b, x + 1);
        }
      }
    }
    return min(a, b);
  }
};

func minSwap(nums1 []int, nums2 []int) int {
  a, b, n := 0, 1, len(nums1)
  for i := 1; i < n; i++ {
    x, y := a, b
    if nums1[i-1] >= nums1[i] || nums2[i-1] >= nums2[i] {
      a, b = y, x+1
    } else {
      b = y + 1
      if nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i] {
        a = min(a, y)
        b = min(b, x+1)
      }
    }
  }
  return min(a, b)
}