聊城做网站低费用,想自己弄个app商城,工作室网站制作,wordpress如何修改自己的网页题目 给定一个数组#xff0c;将数组中的元素向右移动k个位置#xff0c;其中k是非负数。要求如下#xff1a; #xff08;1#xff09;尽可能想出更多的解决方案#xff0c;至少有三种不同的方法可以解决这个问题。 #xff08;2#xff09;使用时间复杂度为O(n)和空间…题目 给定一个数组将数组中的元素向右移动k个位置其中k是非负数。要求如下 1尽可能想出更多的解决方案至少有三种不同的方法可以解决这个问题。 2使用时间复杂度为O(n)和空间复杂度为O(1)的原地算法解决这个问题。 示例 1
输入: [1, 2, 3, 4, 5, 6, 7] 和 k 3输出: [5, 6, 7, 1, 2, 3, 4]解释:向右旋转1步: [7, 1, 2, 3, 4, 5, 6]向右旋转2步: [6, 7, 1, 2, 3, 4, 5]向右旋转3步: [5, 6, 7, 1, 2, 3, 4] 示例 2
输入: [-8, -100, 50, 66] 和 k 2输出: [50, 66, -8, -100]解释:向右旋转1步: [66, -8, -100, 50]向右旋转2步: [50, 66, -8, -100] 解析 这道题主要考察应聘者从多个角度、多个维度分析和思考问题的能力。 最直接、最简单的解决方案当然是“暴力法”也就是每次将数组向右移动一个元素一共旋转k次。向右移动一个元素需要将最后一个元素移动到数组开头然后将其他元素依次右移。“暴力法”的时间复杂度为O(n*k)空间复杂度为O(1)。具体实现可参考下面的示例代码。这里我们使用了Rust标准库中的rotate_right方法它直接提供了按指定步数向右旋转数组的功能使得代码更为简洁。
fn rotate_array(arr: mut [i32], mut k: usize) {let n_len arr.len();k % n_len;arr.rotate_right(k);
}fn print_array(arr: [i32]) {for item in arr.iter() {print!({} , item);}println!();
}fn main() {let mut data [1, 2, 3, 4, 5, 6, 7];rotate_array(mut data, 3);print_array(data);
} “暴力法”的时间复杂度较高我们可以通过以空间换时间的方式来优化时间复杂度。具体做法为使用一个额外的数组来将每个元素放到正确的位置上也就是我们把原本数组里下标为i的元素放到(ik)%数组长度的位置最后我们把新的数组拷贝到原来的数组中。该方法的时间复杂度为O(n)空间复杂度也为O(n)。具体实现可参考下面的示例代码。这里我们使用to_vec()方法来创建原数组的一个拷贝然后通过索引操作和copy_from_slice()方法来完成数据的转移。
fn rotate_array(arr: mut [i32], k: usize) {let n_len arr.len();let mut data_bak arr.to_vec();for i in 0..n_len {data_bak[(i k) % n_len] arr[i];}arr.copy_from_slice(data_bak);
}fn print_array(arr: [i32]) {for item in arr {print!({} , item);}println!();
}fn main() {let mut data vec![1, 2, 3, 4, 5, 6, 7];rotate_array(mut data, 3);print_array(data);
} 实际上解决旋转数组的问题还可以通过三次反转数组来实现。第一次整体反转使原数组后k个元素位于前k个元素中但内部顺序正好相反。第二次反转只需要反转前k个元素。第三次反转只需要反转后n-k个元素。需要注意的是如果k大于数组的长度需要对k取模以保证不会超出数组的范围。 接下来我们来看看如何反转数组。反转数组指的是将数组的顺序颠倒比如给定数组为[1, 2, 3, 4, 5, 6, 7]则反转后的数组为[7, 6, 5, 4, 3, 2, 1]。可以通过双指针法来实现反转先交换数组的第一个数和最后一个数然后交换第二个数和倒数第二个数一直到数组中间即可。该方法的时间复杂度为O(n)空间复杂度也为O(1)。具体实现可参考下面的示例代码。这里我们通过三次反转数组的部分来完成整个数组的旋转。我们还使用了Rust的swap方法来交换数组中的元素并且利用了数组的可变引用mut [i32]来直接修改原数组内容。
fn reverse_array(arr: mut [i32], mut start: usize, mut end: usize) {while start end {arr.swap(start, end);start 1;end - 1;}
}fn rotate_array(arr: mut [i32], k: usize) {let n_len arr.len();let actual_k k % n_len;reverse_array(arr, 0, n_len - 1);reverse_array(arr, 0, actual_k - 1);reverse_array(arr, actual_k, n_len - 1);
}fn print_array(arr: [i32]) {for item in arr {print!({} , item);}println!();
}fn main() {let mut data [1, 2, 3, 4, 5, 6, 7];rotate_array(mut data, 3);print_array(data);
} 总结 一个问题的解决方案可能远不止一种正所谓“条条大路通罗马”如何在众多解决方案中找出最优解实际上非常考验软件开发工程师的综合能力。从多个角度、多个维度分析和思考问题是一种非常有效的思维方式可以帮助我们更全面地理解问题并找到更好更优的解决方案。
