class Solution {
public:
vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {
}
};
6469. 重新放置石块
给你一个下标从 0 开始的整数数组 nums ，表示一些石块的初始位置。再给你两个长度 相等 下标从 0 开始的整数数组 moveFrom 和 moveTo 。
在 moveFrom.length 次操作内，你可以改变石块的位置。在第 i 次操作中，你将位置在 moveFrom[i] 的所有石块移到位置 moveTo[i] 。
完成这些操作后，请你按升序返回所有 有 石块的位置。
注意：
示例 1：
输入：nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5] 输出：[5,6,8,9] 解释：一开始，石块在位置 1,6,7,8 。 第 i = 0 步操作中，我们将位置 1 处的石块移到位置 2 处，位置 2,6,7,8 有石块。 第 i = 1 步操作中，我们将位置 7 处的石块移到位置 9 处，位置 2,6,8,9 有石块。 第 i = 2 步操作中，我们将位置 2 处的石块移到位置 5 处，位置 5,6,8,9 有石块。 最后，至少有一个石块的位置为 [5,6,8,9] 。
示例 2：
输入：nums = [1,1,3,3], moveFrom = [1,3], moveTo = [2,2] 输出：[2] 解释：一开始，石块在位置 [1,1,3,3] 。 第 i = 0 步操作中，我们将位置 1 处的石块移到位置 2 处，有石块的位置为 [2,2,3,3] 。 第 i = 1 步操作中，我们将位置 3 处的石块移到位置 2 处，有石块的位置为 [2,2,2,2] 。 由于 2 是唯一有石块的位置，我们返回 [2] 。
提示：
1 <= nums.length <= 1051 <= moveFrom.length <= 105moveFrom.length == moveTo.length1 <= nums[i], moveFrom[i], moveTo[i] <= 109i 步操作时，moveFrom[i] 处至少有一个石块。原站题解
php 解法, 执行用时: 291 ms, 内存消耗: 35.4 MB, 提交时间: 2024-07-24 09:03:37
class Solution {
/**
* @param Integer[] $nums
* @param Integer[] $moveFrom
* @param Integer[] $moveTo
* @return Integer[]
*/
function relocateMarbles($nums, $moveFrom, $moveTo) {
$arr = [];
foreach ($nums as $n) {
$arr[$n] = 1;
}
for ($i = 0; $i < count($moveFrom); $i++) {
if ($moveFrom[$i] == $moveTo[$i]) continue;
$arr[$moveTo[$i]] = 1;
unset($arr[$moveFrom[$i]]);
}
$arr = array_keys($arr);
sort($arr);
return $arr;
}
}
rust 解法, 执行用时: 28 ms, 内存消耗: 4.1 MB, 提交时间: 2024-07-24 09:02:53
use std::collections::HashSet;
impl Solution {
pub fn relocate_marbles(nums: Vec<i32>, move_from: Vec<i32>, move_to: Vec<i32>) -> Vec<i32> {
let mut set = nums.into_iter().collect::<HashSet<_>>();
for (f, t) in move_from.into_iter().zip(move_to) {
set.remove(&f);
set.insert(t);
}
let mut ans = set.into_iter().collect::<Vec<_>>();
ans.sort_unstable();
ans
}
}
javascript 解法, 执行用时: 182 ms, 内存消耗: 75.5 MB, 提交时间: 2024-07-24 09:02:33
/**
* @param {number[]} nums
* @param {number[]} moveFrom
* @param {number[]} moveTo
* @return {number[]}
*/
var relocateMarbles = function(nums, moveFrom, moveTo) {
const set = new Set(nums);
for (let i = 0; i < moveFrom.length; i++) {
set.delete(moveFrom[i]);
set.add(moveTo[i]);
}
const ans = Array.from(set);
ans.sort((a, b) => a - b);
return ans;
};
java 解法, 执行用时: 53 ms, 内存消耗: 55.7 MB, 提交时间: 2023-07-10 09:32:20
class Solution {
public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
Set<Integer> posSet = new HashSet<>();
for (int num : nums) {
posSet.add(num);
}
for (int i = 0; i < moveFrom.length; i++) {
posSet.remove(moveFrom[i]);
posSet.add(moveTo[i]);
}
List<Integer> res = new ArrayList(posSet);
Collections.sort(res);
return res;
}
}
cpp 解法, 执行用时: 336 ms, 内存消耗: 174.6 MB, 提交时间: 2023-07-10 09:31:36
// 哈希模拟
class Solution {
public:
vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {
map<int,int> cnt;
for(int i = 0 ; i < nums.size() ;i++){
cnt[nums[i]]++;
}
for(int i = 0 ;i < moveFrom.size();i++){
if(cnt[moveFrom[i]] > 0 && moveFrom[i] != moveTo[i]){
cnt[moveTo[i]] += cnt[moveFrom[i]];
cnt[moveFrom[i]] = 0;
}
}
vector<int> ans;
for(auto & it: cnt) if(it.second > 0) ans.push_back(it.first);
return ans;
}
};
golang 解法, 执行用时: 172 ms, 内存消耗: 10.9 MB, 提交时间: 2023-07-10 09:30:00
func relocateMarbles(nums, moveFrom, moveTo []int) []int {
set := map[int]struct{}{}
for _, x := range nums {
set[x] = struct{}{}
}
for i, x := range moveFrom {
delete(set, x)
set[moveTo[i]] = struct{}{}
}
ans := make([]int, 0, len(set))
for x := range set {
ans = append(ans, x)
}
sort.Ints(ans)
return ans
}
python3 解法, 执行用时: 112 ms, 内存消耗: 35 MB, 提交时间: 2023-07-10 09:29:44
'''
模拟即可
由于每次把moveFrom[i]的石块全部移走，所以无需维护nums[i]
'''
class Solution:
def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:
cnt = set(nums)
for f, t in zip(moveFrom, moveTo):
cnt.remove(f)
cnt.add(t)
return sorted(cnt)