A classic coding problem in the interview: Leetcode 189

Here is a solution for leetcode 189, Rotate Array. It's not hard but it frequently appears in the interview. Read it if you're not familiar with it.

Problem: 

　　Given an array, rotate the array to the right by k steps, where k is non-negative. Do it in place.

　　Input: nums = [1,2,3,4,5,6,7], k = 3

　　Output: [5,6,7,1,2,3,4]

Solution:

　　We can see that after rotation the last k numbers in the original array become the first k numbers. Therefore we first reverse the entire array, then reverse the first k numbers, and then reverse the remaining part of the array.

Code is as follows:

class Solution {
    public void rotate(int[] nums, int k) {
        int n=nums.length;
        k=k%n;
        reverse(nums,0,n-1);
        reverse(nums,0,k-1);
        reverse(nums,k,n-1);
    }
    
    private void reverse(int[] a,int lo,int hi){
        while(lo<hi){
            int t=a[lo];
            a[lo]=a[hi];
            a[hi]=t;
            lo++;hi--;
        }
    }
}

• 还没有人评论，欢迎说说您的想法！

相关课程

英特尔® OpenVINO™工具套件初级课程

293020 0元 限免

英特尔 OpenCV 初级认证课程

7701 0元 限免

基于 OpenVINO™ 的 AI 视觉应用基础课

56019 0元 限免