情侶牽手
N 對情侶坐在連續排列的 2N 個座位上，想要牽到對方的手， 計算最少交換座位的次數，以便每對情侶可以并肩坐在一起， 一次交換可選擇任意兩人，讓他們站起來交換座位，
人和座位用 0 到 2N-1 的整數表示，情侶們按順序編號，第一對是 (0, 1)，第二對是 (2, 3)，以此類推，最后一對是 (2N-2, 2N-1)，這些情侶的初始座位 row[i] 是由最初始坐在第 i 個座位上的人決定的，
示例 1:
輸入: row = [0, 2, 1, 3]
輸出: 1
解釋: 我們只需要交換row[1]和row[2]的位置即可，
示例 2:
輸入: row = [3, 2, 0, 1]
輸出: 0
解釋: 無需交換座位，所有的情侶都已經可以手牽手了，
解題思路
該題可使用貪心的思想進行操作，從題目中得到情侶們按順序編號，第一對是 (0, 1)，第二對是 (2, 3)，以此類推，最后一對是 (2N-2, 2N-1)，都是一個偶數搭配一個奇陣列成一對情侶，所以若當前遍歷的值為偶數或 0，則它所對應的情侶應該是當前元素值 + 1，若當前遍歷的值為奇數，則它所對應的情侶應該是當前元素值 - 1，本體的操作步驟如下：
(1) 首先從 row 陣列的第一個元素開始判斷
- 若是偶數或 0，則向后遍歷找到 row[i] + 1 的值保存下來與 row[i + 1] 交換位置----changeNum + 1
- 若是奇數，則向后遍歷找到 row[i] - 1 的值保存下來與 row[i + 1] 交換位置----changeNum + 1
(2) 交換完后當前 i 位置上的情侶已經配對，則繼續遍歷下一對情侶，若情侶不需要交換位置就已經牽手了，則 i++，并且直接 continue，進行下一對情侶的判斷，
代碼
class Solution {
//貪心
/*
1.先從row陣列的第一個元素開始
若是偶數或0，則向后遍歷找到row[i] + 1的值保存下來與row[i + 1]交換位置----changeNum + 1
若是奇數，則向后遍歷找到row[i] - 1的值保存下來與row[i + 1]交換位置----changeNum + 1
2.此時，繼續像之前一樣遍歷陣列---直到結束
*/
public int minSwapsCouples(int[] row) {
int n = row.length;
int changeNum = 0;
int record = 0;
for (int i=0;i<n;i++) {
if (row[i] % 2 != 0) {
//已經牽手
if (row[i + 1] == row[i] - 1) {
i++;//直接后移
continue;
} else {
for (int j=i+1;j<n;j++) {
if (row[j] == row[i] - 1) {
record = row[j];
row[j] = row[i + 1];
row[i + 1] = record;
changeNum++;
break;
}
}
}
} else {
if (row[i + 1] == row[i] + 1) {
i++;
continue;
} else {
for (int j=i+1;j<n;j++) {
if (row[j] == row[i] + 1) {
record = row[j];
row[j] = row[i + 1];
row[i + 1] = record;
changeNum++;
break;
}
}
}
}
}
return changeNum;
}
}
空間復雜度：沒有額外新開辟任何空間，復雜度為O(1)
時間復雜度：因為有 for 回圈的嵌套，復雜度為O(n2)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259830.html
標籤：其他
上一篇：android音視頻【九】音頻硬編解碼pcm&aac&wav
下一篇：演算法實作(排列 組合 二分圖)