本文主要是介绍leetcode解题系列:翻转数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Q:Problem: Rotate an array of n elements to the right by k steps. For example, 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?
a:
1、first method:新建一个数组,将数据保存存放结果。时间复杂度为:n,空间复杂度:n
public static void rotateArray(int array[], int k) {if(k <= 0)return; if(k > array.length) {k = k % array.length; }int result[] = new int[array.length]; for(int i=0; i<k; i++) {result[i] = array[array.length - k + i]; }int j =0; for(int i= k; i<array.length; i++) {result[i] = array[j]; j++; }System.arraycopy(result, 0, array, 0, array.length); }2、second method : 类是冒泡算法:时间:n * k,空间:1
public static void bubbleRotate(int array[], int k) {for(int i=k; i< array.length; i++) {int tempValue = array[i]; for(int j = i ; j > 0; j --) { // int temp = array[j]; array[j] = array[j -1]; // array[j-1] = temp; }array[0] = tempValue; }}3、third method :翻转,时间为 n,空间为 1
Assuming we are given {1,2,3,4,5,6} and order 2. The basic idea is:
1. Divide the array two parts: 1,2,3,4 and 5, 6 2. Rotate first part: 4,3,2,1,5,6 3. Rotate second part: 4,3,2,1,6,5 4. Rotate the whole array: 5,6,1,2,3,4
public static void reverseArray(int array[], int k) {reverse(array, 0, k-1); reverse(array, k, array.length -1); reverse(array, 0, array.length -1); }public static void reverse(int array[], int left, int right) {while (left < right) {int temp = array[left]; array[left] = array[right]; array[right] = temp; right--; left++; }
ps:贴下代码
https://code.csdn.net/snippets/775491.git
这篇关于leetcode解题系列:翻转数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!