2023-04-16:给定一个长度为N的数组,值一定在0~N-1范围,且每个值不重复比如,arr = [4, 2, 0, 3, 1]
数组 一个 2023 重复 长度 16 范围 一定
2023-06-13 09:18:39 时间
2023-04-16:给定一个长度为N的数组,值一定在0~N-1范围,且每个值不重复
比如,arr = 4, 2, 0, 3, 1
0 1 2 3 4
把0想象成洞,任何非0数字都可以来到这个洞里,然后在原本的位置留下洞
比如4这个数字,来到0所代表的洞里,那么数组变成 :
arr = 0, 2, 4, 3, 1
也就是原来的洞被4填满,4走后留下了洞
任何数字只能搬家到洞里,并且走后留下洞
通过搬家的方式,想变成有序的,有序有两种形式
比如arr = 4, 2, 0, 3, 1,变成
0, 1, 2, 3, 4或者1, 2, 3, 4, 0都叫有序。
返回变成任何一种有序的情况都可以,最少的数字搬动次数。
来自谷歌。
答案2023-04-16:
解题步骤:
- 对于第一种有序情况,我们可以模拟交换排序的过程,算出需要交换的次数,具体实现见函数sortArray()。
- 对于第二种有序情况,我们可以先倒序遍历数组,找出每个数需要移动的最小距离,从而计算出需要移动的次数。
- 最后比较这两种情况下的最小搬动次数,返回较小值即可。
注意事项:
- 需要记录每个数是否被遍历过,以防止重复计算。
- 数字只能搬家到洞里,并且走后留下洞,因此在交换过程中需要记录其中一个数字所在的位置作为洞的位置。
golang代码如下:
package main
import "fmt"
func sortArray(nums []int) int {
// 长度n
// ans1 : 0 1 2 3 4 .... 这种样子,至少交换几次
// ans2 : 1 2 3 4 .... 0 这种样子,至少交换几次
// m : 每个环里有几个数
// next : 往下跳的位置
n := len(nums)
ans1, ans2 := 0, 0
touched := make([]bool, n)
// 0 1 2 3 4...
for i := 0; i < n; i++ {
if !touched[i] {
touched[i] = true
m := 1
next := nums[i]
for next != i {
m++
touched[next] = true
next = nums[next]
}
// m 当前环,有几个数
// 6
// 6
if m > 1 {
if i == 0 {
ans1 += m - 1
} else {
ans1 += m + 1
}
}
}
}
touched = make([]bool, n)
// 1 2 3 4 ... 0
// i == n-1
for i := n - 1; i >= 0; i-- {
if !touched[i] {
touched[i] = true
m := 1
// next
// 5
// i(8) -> 4
// 0
// i(8) -> n-1
next := nums[i]
if next == 0 {
next = n - 1
} else {
next--
}
for next != i {
m++
touched[next] = true
if nums[next] == 0 {
next = n - 1
} else if next > 0 {
next--
} else {
next = n - 1
}
}
if m > 1 {
if i == n-1 {
ans2 += m - 1
} else {
ans2 += m + 1
}
}
}
}
if ans1 < ans2 {
return ans1
}
return ans2
}
func main() {
nums := []int{4, 2, 0, 3, 1}
ans := sortArray(nums)
fmt.Println(ans) // 输出 3
}
rust代码如下:
fn sort_array(nums: &[i32]) -> i32 {
let n = nums.len() as i32;
let mut ans1 = 0;
let mut ans2 = 0;
let mut touched = vec![false; n as usize];
for i in 0..n {
if !touched[i as usize] {
touched[i as usize] = true;
let mut m = 1;
let mut next = nums[i as usize];
while next != i {
m += 1;
touched[next as usize] = true;
next = nums[next as usize];
}
if m > 1 {
if i == 0 {
ans1 += m - 1;
} else {
ans1 += m + 1;
}
}
}
}
touched = vec![false; n as usize];
for i in (0..n).rev() {
if !touched[i as usize] {
touched[i as usize] = true;
let mut m = 1;
let mut next = if nums[i as usize] == 0 {
n - 1
} else {
nums[i as usize] - 1
};
while next != i {
m += 1;
touched[next as usize] = true;
next = if nums[next as usize] == 0 {
n - 1
} else {
nums[next as usize] - 1
};
}
if m > 1 {
if i == n - 1 {
ans2 += m - 1;
} else {
ans2 += m + 1;
}
}
}
}
ans1.min(ans2)
}
fn main() {
let nums = vec![4, 2, 0, 3, 1];
let ans = sort_array(&nums);
println!("{}", ans); // 输出 3
}
相关文章
- 2022-09-05:作为国王的统治者,你有一支巫师军队听你指挥。 :给你一个下标从 0 开始的整数数组 strength , 其中 strength[i] 表
- php案例:创建一个数组cookie
- 两个数组合并成一个数组 请把两个数组 ['A1', 'A2', 'B1', 'B2', 'C1', 'C2', 'D1', 'D2'] 和 ['A', 'B', 'C', 'D'],合并为 ['...
- js比较前后两个数组对象的差异
- js 数组去除重复数据-5 个提升你 JS 编码水平的实例
- 2022-12-06:定义一个概念叫“变序最大和“ “变序最大和“是说一个数组中,每个值都可以减小或者不变, 在必须把整体变成严
- 2023-03-16:给定一个由 0 和 1 组成的数组 arr ,将数组分成 3 个非空的部分, 使得所有这些部分表示相同的二进制值。 如果可以做到,请返回任
- 2023-03-18:给定一个长度n的数组,每次可以选择一个数x, 让这个数组中所有的x都变成x+1,问你最少的操作次数, 使得这个数组变成一个非降数组。 n
- Java 数组的三种创建方法详解编程语言
- Oracle 数组变量赋值方法简介(oracle给数组赋值)
- Redis实现数组快速查询(redis 查询数组)
- js对象数组按属性快速排序
- php下将多个数组合并成一个数组的方法与实例代码
- php数组函数序列之array_push()数组尾部添加一个或多个元素(入栈),返回新长度。
- javascript将数组插入到另一个数组中的代码
- php函数array_merge用法一例(合并同类数组)
- js克隆对象、数组的常用方法介绍
- Javascript中克隆一个数组的实现代码
- Javascript连接多个数组不用concat来解决