当前位置： 面试刷题>> 移动石子 (经典算法题500道)
### 题目描述
**移动石子**
在一个一维的直线上，有`n`个石子排成一列，每个石子都有一个唯一的编号从`1`到`n`。现在你需要进行一系列的操作来移动这些石子，使得它们按照从小到大的顺序排列（即编号`1`的石子在最左边，编号`n`的石子在最右边）。
每次操作，你可以选择相邻的两个石子进行交换。但是，交换两个石子需要支付一定的代价，代价等于这两个石子编号的差的绝对值。
例如，如果石子排列为`[3, 1, 2]`，你需要至少两步才能将它们排成`[1, 2, 3]`：
1. 交换`3`和`1`（代价为`|3-1| = 2`），得到`[1, 3, 2]`
2. 交换`3`和`2`（代价为`|3-2| = 1`），得到`[1, 2, 3]`
总代价为`2 + 1 = 3`。
**问题**：给定一个初始的石子排列数组，编写一个函数来计算并返回将所有石子按照顺序排列所需的最小代价。
### 示例代码
#### PHP 示例
```php
function minSwapCost($stones) {
$n = count($stones);
$pos = array_flip($stones); // 创建一个位置映射，以便快速查找每个石子的索引
$cost = 0;
for ($i = 0; $i < $n - 1; $i++) {
$target = $i + 1; // 当前位置应有的目标石子编号
while ($stones[$i] != $target) {
$nextPos = $pos[$target]; // 查找目标石子当前的位置
// 交换当前石子与目标石子
list($stones[$i], $stones[$nextPos]) = array($stones[$nextPos], $stones[$i]);
$pos[$stones[$i]] = $i; // 更新位置映射
$pos[$stones[$nextPos]] = $nextPos;
$cost += abs($stones[$i] - $stones[$nextPos]); // 累加交换代价
$target++; // 如果当前位置的石子不是目标石子，则尝试下一个目标石子
}
}
return $cost;
}
// 示例
$stones = [3, 1, 2];
echo minSwapCost($stones); // 输出: 3
```
**注意**：上述PHP代码示例是一个直观解法，但在真实面试中，可能需要一个更高效的解法，特别是考虑到题目通常期望时间复杂度较低的算法。上述解法为了直观展示思路，并未优化。
#### Python 示例
```python
def minSwapCost(stones):
n = len(stones)
pos = {stone: i for i, stone in enumerate(stones)} # 位置映射
cost = 0
for i in range(n):
target = i + 1
while stones[i] != target:
next_pos = pos[target]
stones[i], stones[next_pos] = stones[next_pos], stones[i]
pos[stones[i]] = i
pos[stones[next_pos]] = next_pos
cost += abs(stones[i] - stones[next_pos])
target += 1
return cost
# 示例
stones = [3, 1, 2]
print(minSwapCost(stones)) # 输出: 3
```
#### JavaScript 示例
```javascript
function minSwapCost(stones) {
const n = stones.length;
const pos = {};
for (let i = 0; i < n; i++) {
pos[stones[i]] = i; // 创建位置映射
}
let cost = 0;
for (let i = 0; i < n - 1; i++) {
let target = i + 1;
while (stones[i] !== target) {
const nextPos = pos[target];
// 交换石子
[stones[i], stones[nextPos]] = [stones[nextPos], stones[i]];
// 更新位置映射
pos[stones[i]] = i;
pos[stones[nextPos]] = nextPos;
cost += Math.abs(stones[i] - stones[nextPos]);
target++;
}
}
return cost;
}
// 示例
const stones = [3, 1, 2];
console.log(minSwapCost(stones)); // 输出: 3
```
以上代码示例展示了如何在PHP、Python和JavaScript中计算移动石子所需的最小代价。在实际面试中，根据题目的具体要求，可能还需要考虑其他优化方法，比如利用贪心算法或排序的性质来减少不必要的交换操作。