FilesExpand file tree

master

/

RotateArray.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

55 lines (51 loc) · 1.7 KB

master

/

RotateArray.java

Copy path

Top

File metadata and controls

• Code
• Blame

55 lines (51 loc) · 1.7 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

// Source : https://leetcode.com/problems/rotate-array/description/

// Author : Tianming Cao

// Date : 2018-02-02

/**********************************************************************************

* 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].

*

* Note:

* Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

*

* Hint:

* Could you do it in-place with O(1) extra space?

* Related problem: Reverse Words in a String II

*

**********************************************************************************/

package rotateArray;

/**********************************************************************************

*

* For example, with n = 9 and k = 4, the array is [1,2,3,4,5,6,7,8,9]

* The train of thought is:

* 1. Reverse 1-5 to [5,4,3,2,1]

* 2. Reverse 6-9 to [9,8,7,6]

* 3. Reverse the entire array [5,4,3,2,1,9,8,7,6] to [6,7,8,9,1,2,3,4,5]

* It's a liner time and in-place algorithm

*

**********************************************************************************/

public class RotateArray {

public void rotate(int[] nums, int k) {

//bounds check

if (nums == null || nums.length == 0 || k == 0) {

return;

}

int n = nums.length;

//k may be larger than n

k = k % n;

rotateRange(0, n - k - 1, nums);

rotateRange(n - k, n - 1, nums);

rotateRange(0, n - 1, nums);

}

private void rotateRange(int start, int end, int[] array) {

for (int i = start, j = end; i < j; i++, j--) {

swap(array, i, j);

}

}

private void swap(int[] array, int i, int j) {

int t = array[i];

array[i] = array[j];

array[j] = t;

}

}