问题描述
我要测试以下问题:
例如,在n = 7和k = 3的情况下,将数组[1,2,3,4,5,6,7]旋转为 [5,6,7,1,2,3,4].您知道多少种方法可以解决此问题?
For instance, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. How many different ways do you know to solve this problem?
我在中间数组中的解决方案:
My solution in intermediate array:
在Space为O(n)
并且时间为O(n)
的情况下,我可以创建一个新数组,然后将元素复制到该新数组中.然后使用System.arraycopy()
更改原始数组.
With Space is O(n)
and time is O(n)
, I can create a new array and then copy elements to the new array. Then change the original array by using System.arraycopy()
.
public void rotate(int[] nums, int k) {
if(k > nums.length)
k=k%nums.length;
int[] result = new int[nums.length];
for(int i=0; i < k; i++){
result[i] = nums[nums.length-k+i];
}
int j=0;
for(int i=k; i<nums.length; i++){
result[i] = nums[j];
j++;
}
System.arraycopy( result, 0, nums, 0, nums.length );
}
但是有没有更好的方法可以通过O(1
)空间中的气泡旋转(如气泡排序)来实现呢?
But is there a better way we can do it with bubble rotate(like bubble sort) in O(1
) space?
推荐答案
您不需要for
-循环.
public int[] rotate(int[] nums, int k) {
if(k > nums.length)
k=k%nums.length;
int[] result = new int[nums.length];
System.arraycopy( nums, k+1, result, 0, k );
System.arraycopy( nums, 0, result, k+1, nums.length-1 );
//Case 1: The rotated array will be assigned to the given array "nums"
nums = result;
return result; //Case 2: method returns the rotated array
}
可以在这里 http:找到arraycopy的规范. //docs.oracle.com/javase/7/docs/api/java/lang/System.html
不是睾丸.方法旋转O(1)的整体复杂性.
Not testet. The overall complexity of method rotate O(1).
如果您的问题是关于所有可能的排列,请在这里查看用于置换数字列表的Java代码
If your question was about all possible permutation have a look hereJava Code for permutations of a list of numbers
另一项建议是查看 Java集合API ,该API提供了许多复杂的数据结构和常见的排序算法,这些都是以非常有效的方式实现的.
Another advise is to check out the Java Collection API which provides many sophisticated data structures and common sort algorithms, which are all implemented in a very efficient way.
由于评论而编辑.
该方法返回旋转数组.您可以在外部方法中使用该方法,例如:(只需伪代码)
The method returns a rotated array. You can use the method within an outer method like this: (Just pseudo-code)
void rotator(int[] nums) {
int rotated[] = nums;
//Can be invoked iteraritve or within a loop like this
rotated = rotate(rotated, 3);
}
这篇关于如何旋转数组?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!