Giải bài 189 Rotate Array O(N)

[ltd (Lê Trần Đạt)]

Đề bài:

• https://leetcode.com/problems/rotate-array/

Bài giải:

Java code

public class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Python Code

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        def reverse(nums, i, j):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i + 1, j - 1
        n = len(nums)
        if n == 0: return
        k %= n
        reverse(nums, 0, n - 1)
        reverse(nums, 0, k - 1)
        reverse(nums, k, n - 1)

Nhờ các bạn code lại với các ngôn ngữ khác

[Dao_An (Đào An)]

Bên này có gì khác bên codewars, codesignal ko anh .

[anon12276517]

Trước em cũng từng làm bài này, góp vui vào với mọi người ạ

Block swap algorithm for array rotation

Bạn có thể để ý: d = 7 thì sau khi xoay ta sẽ được một mảng y hệt như cũ, vậy nên chỉ cần xoay d' = d % 7 là được Tiện mình cũng đưa ra giải thuật bày này luôn Nếu bạn để ý chút thì sẽ thấy Các phần tử cần xoay sẽ di chuyển về vị trí = size - d + vị trí của số đó trong mảng Còn vị trí của các phần tử còn lại sẽ thành A[d + vị trí của số đó trong mảng] Nếu bạn vẫn chưa hiểu thì có thể xem qua code của mình ở đây nhé

[Dao_An (Đào An)]

Bên này ưu điểm là có solution nhưng mà bằng có mỗi Java nhỉ. Muốn xem solution của ngôn ngữ khác lại phải search .

[hungaya (Hung)]

JavaScript

function rotate(nums, k) {
  function reverse(start, end) {
    while (start < end) {
      [ nums[start], nums[end] ] = [ nums[end], nums[start] ];
      start++; end--;
    }
  }

  k %= nums.length;
  reverse(0, nums.length - 1);
  reverse(0, k - 1);
  reverse(k, nums.length - 1);
}

PHP

class Solution
{
    public function rotate($nums, $k)
    {
        $len = count($nums);
        $k %= $len;

        $this->reverse($nums, 0, $len - 1);
        $this->reverse($nums, 0, $k - 1);
        $this->reverse($nums, $k, $len - 1);
    }

    private function reverse($nums, $start, $end)
    {
        while ($start < $end) {
            $temp = $nums[$start];
            $nums[$start] = $nums[$end];
            $nums[$end] = $temp;
            $start++;
            $end--;
        }
    }
}

Ruby

class Solution
  def rotate(nums, k)
    k %= nums.length
    reverse(nums, 0, nums.length - 1)
    reverse(nums, 0, k - 1)
    reverse(nums, k, nums.length - 1)
  end

  private
    def reverse(nums, head, last)
      while head < last do
        nums[last], nums[head] = nums[head], nums[last]
        head += 1
        last -= 1
      end
    end
end

Swift

class Solution {
    func rotate(_ nums: [Int], repeat k: Int) {
        k %= nums.count
        reverse(nums, start: 0, end: nums.count - 1)
        reverse(nums, start: 0, end: k - 1)
        reverse(nums, start: k, end: nums.count - 1)
    }

    private func reverse(_ nums: [Int], start: Int, end: Int) {
        while start < end {
            swap(nums[start], nums[end])
            start += 1, end -= 1;
        }
    }
}

Scala

class Solution
  def rotate(nums: Array[Int], k: Int) {
    k %= nums.length
    reverse(nums, 0, nums.length - 1)
    reverse(nums, 0, k - 1)
    reverse(nums, k, nums.length - 1)
  }

  private def reverse(nums: Array[Int], start: Int, end: Int) {
    while (start < end) {
      val temp = nums(start)
      nums(start) = nums(end)
      nums(end) = temp
      start++
      end--
    }
  }
}

Erlang

-module(solution).
-import(lists, [sublist/2, sublist/3, reverse/1]).
-export([rotate/2]).

rotate(Nums, K) ->
  NumsRev = reverse(Nums),
  PreNums = reverse(sublist(NumsRev, K)),
  LastNums = reverse(sublist(NumsRev, K, length(NumsLen)),
  PreNums ++ LastNums.
  

[Dao_An (Đào An)]

Góp vui với Rust

impl Solution {
    pub fn rotate(nums: &mut Vec<i32>, k: i32) -> Vec<i32> {
        for _ in 0..k {
            nums.insert(0, nums[nums.len() - 1]);
            nums.pop();
        }
        Vec::from(&nums[..])
    }
}

[japananh (Trần Nhật Anh)]

Javascript

    var rotate = function(nums, k) {    
    for (let i = 0; i < k ; i++) {
        nums.unshift(nums[nums.length - 1]);
        nums.pop();        
    }    
    
    return nums;     
};

[rogp10]

Hai đoạn code trên đều O(N^2)

[Huy_Nguyen1 (Huy Nguyễn)]

Mặc dù không đúng yêu cầu của leetcode lắm nhưng em nghĩ cũng khá hay ho
Scala:

val shiftRight = (arr: Array[Int], k: Int) => Iterator.continually(arr.iterator).flatten.drop(arr.length - k % arr.length).take(arr.length)
val a = Array(1,2,3,4)
shiftRight(a, 2).foreach(print) // 3412

[Nguyen_Nhan_Tinh (bình thường)]

C++

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        int tmp;
        while (start < end) {
            tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }
    void rotate(vector<int>& nums, int k) {
        int _step;
        _step = k % (nums.size());
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, _step - 1);
        reverse(nums, k, nums.size() - 1);
    }
};