526互联

[LeetCode] 2340. Minimum Adjacent Swaps to Make a Valid Array

发布时间 2023-07-20 07:00:51作者: CNoodle

You are given a 0-indexed integer array nums.

Swaps of adjacent elements are able to be performed on nums.

A valid array meets the following conditions:

  • The largest element (any of the largest elements if there are multiple) is at the rightmost position in the array.
  • The smallest element (any of the smallest elements if there are multiple) is at the leftmost position in the array.

Return the minimum swaps required to make nums a valid array.

Example 1:

Input: nums = [3,4,5,5,3,1]
Output: 6
Explanation: Perform the following swaps:
- Swap 1: Swap the 3rd and 4th elements, nums is then [3,4,5,3,5,1].
- Swap 2: Swap the 4th and 5th elements, nums is then [3,4,5,3,1,5].
- Swap 3: Swap the 3rd and 4th elements, nums is then [3,4,5,1,3,5].
- Swap 4: Swap the 2nd and 3rd elements, nums is then [3,4,1,5,3,5].
- Swap 5: Swap the 1st and 2nd elements, nums is then [3,1,4,5,3,5].
- Swap 6: Swap the 0th and 1st elements, nums is then [1,3,4,5,3,5].
It can be shown that 6 swaps is the minimum swaps required to make a valid array.
Example 2: 
Input: nums = [9]
Output: 0
Explanation: The array is already valid, so we return 0. 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

生成有效数组的最小交换次数。

题意是请你将 input 数组中的最小值移动到数组最左边，把最大值移动到数组的最右边。移动的方式只能是和邻居元素 swap，请你返回最少的移动次数。

思路是贪心。下面我根据例子仔细说一下思考过程。

注意第一个例子，最小元素是 1，那么没的说，我们只能老老实实把 1 一步一步往左边 swap，对于这个 1，他的 swap 的次数是他的 index - 0 = index 步；但是对于最大元素 5 来说，他出现了不止一次，而且因为之前涉及到跟 1 有交换位置，所以为了 swap 的步数尽量少，我们需要选择位于数组最右边的最大值，因为最右边的那个最大值是离数组最后一个 index 最近的。所以这道题我们移动的步数 = 最左边的最小值到 index = 0 的距离 + 最右边的最大值到 index = n - 1 的距离（n 是数组长度）。同时注意如果最小值在最大值右侧，在 swap 的过程中需要少算一步，因为当我们将最小值往左 swap 的时候，会经过这个最大值。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int minimumSwaps(int[] nums) {
 3         // corner case
 4         int n = nums.length;
 5         if (n == 1) {
 6             return 0;
 7         }
 8 
 9         // normal case
10         int min = Integer.MAX_VALUE;
11         int max = Integer.MIN_VALUE;
12         for (int i = 0; i < n; i++) {
13             if (nums[i] < min) {
14                 min = Math.min(min, nums[i]);
15             }
16             if (nums[i] > max) {
17                 max = Math.max(max, nums[i]);
18             }
19         }
20 
21         // min和max有可能有多个，要找到最左边的min和最右边的max
22         int minIndex = 0;
23         int maxIndex = 0;
24         for (int i = 0; i < n; i++) {
25             if (nums[i] == min) {
26                 minIndex = i;
27                 break;
28             }
29         }
30         for (int i = n - 1; i >= 0; i--) {
31             if (nums[i] == max) {
32                 maxIndex = i;
33                 break;
34             }
35         }
36 
37         // 如果最小值在左，最大值在右
38         if (minIndex <= maxIndex) {
39             return minIndex + (n - maxIndex);
40         }
41         // 如果最小值在右，最大值在左，需要少一步
42         return minIndex + (n - maxIndex) - 1;
43     }
44 }

 

LeetCode 题目总结