Problem Statement: A 0-indexed
integer array nums is given.
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
Solution:
class Solution {
public int minimumSwaps(int[] nums) {
int min = Arrays.stream(nums).min().getAsInt();
int max = Arrays.stream(nums).max().getAsInt();
int count = 0;
while
(nums[0] !=
min && nums[nums.length-1] !=
max && count < 2 * nums.length)
{
var numsList = Arrays.stream(nums).boxed().collect(Collectors.toList());
var end = numsList.lastIndexOf(max);
for (int i =
end; i < nums.length-1; i++)
{
swap(nums, i, i+1);
count++;
}
numsList = Arrays.stream(nums).boxed().collect(Collectors.toList());
var start = numsList.indexOf(min);
for (int j =
start; j >= 1; j--) {
swap(nums, j, j-1);
count++;
}
}
return
count;
}
public void swap (int[] nums, int i, int j) {
int temp =
nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
Input
nums =
[3,4,5,5,3,1]
Output
6
Expected
6
Input
nums =
[9]
Output
0
Expected
0
