跳到主要内容

元素交换

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] 是否被交换就可以了。这是因为要使得序列严格递增，每个元素只要大于它之前的那个元素就行。这样以来，我们就可以用动态规划的方法来解决这个问题。

  1. 状态定义:

    • dp1 表示数组A和B满足前i-1 个元素分别严格递增，并且A[i-1]和B[i-1]未被交换的最小次数

    • dp2 表示A[i-1]和B[i-1]被交换的最小交换次数

    • 通过状态转移得到temp1 与 temp2

  2. 状态转移方程:

    • 如果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);

  3. 问题答案: 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)。