元素交换
ES6 写法
两个元素交换
let a=3;
let b=5;
[a,b]=[b,a];
console.log(a,b);
三个元素交换
let c=10;
let d=20;
let e=30;
[c,d,e]=[d,e,c];
console.log(c,d,e);
使用数组API交换元素
array.splice(index1, 1 , array[index2])
会将 index1
位置上的元素替换为 index2
位置的元素,同时返回 [array[index1]]
(注意此时返回的是数组,所以在代码中加入了扩展运算符...
将数组转为参数序列)。再利用同样的方式将index2
位置上的元素替换为被删除的原数组的array[index1]
的值。完成交换
array.splice(index2,1,...array.splice(index1, 1 , array[index2]));
使序列递增的最小交换次数
我们有两个长度相等且不为空的整型数组 A 和 B 。
我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。
在交换过一些元素之后,数组 A 和 B 都应该是严格递增的(数组严格递增的条件仅为A[0] < A[1] < A[2] < ... < A[A.length - 1]
)。
给定数组 A 和 B ,请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。
示例1:
示例:
输入: A = [1,3,5,4], B = [1,2,3,7]
输出: 1
解释:
交换 A[3] 和 B[3] 后,两个数组如下:
A = [1, 3, 5, 7] , B = [1, 2, 3, 4]
两个数组均为严格递增的。
方案 动态规划
思路: 我们在判断 A[i] 和 B[i] 是否交换时,只需要考虑它们之前的一个元素 A[i - 1] 和 B[i - 1] 是否被交换就可以了。这是因为要使得序列严格递增,每个元素只要大于它之前的那个元素就行。这样以来,我们就可以用动态规划的方法来解决这个问题。
-
状态定义:
-
dp1 表示数组A和B满足前
i-1
个元素分别严格递增,并且A[i-1]
和B[i-1]
未被交换的最小次数 -
dp2 表示
A[i-1]
和B[i-1]
被交换的最小交换次数 -
通过状态转移得到
temp1
与temp2
-
-
状态转移方程:
-
如果
A[i-1] < B[i-1]
&&A[i] < B[i]
:-
temp1=min(temp1,dp1)
; -
temp2=min(temp2,dp2+1)
;
-
-
如果
A[i-1] < B[i]
&&B[i-1] < A[i]
:-
temp1=min(temp1,dp2)
; -
temp2=min(temp1,dp1+1)
;
-
-
-
问题答案: dp1 和 dp2 中的最小值
function minSwap(nums1, nums2) {
let dp1=0;
let dp2=1;
const len1=nums1.length;
const len2=nums2.length;
for(let i=1;i<len1;i++){
let temp1=Infinity;
let temp2=Infinity;
if(nums1[i-1]<nums1[i]&&nums2[i-1]<nums2[i]){
temp1=Math.min(dp1,temp1);
temp2=Math.min(dp2+1,temp2);
}
if(nums1[i-1]<nums2[i]&&nums2[i-1]<nums1[i]){
temp1=Math.min(temp1,dp2);
temp2=Math.min(temp2,dp1+1);
}
dp1=temp1;
dp2=temp2;
}
return Math.min(dp1,dp2);
};
性能分析:
- 时间复杂度:O(N)。
- 空间复杂度:O(1)。