Hello, everyone. Today, I would like to share with you the next LeetCode medium difficulty problem [Rotate an array].

Here is mainly to share ideas and comments, for you to better understand the problem solution, the code part is to refer to LeetCode translated into javascript code,

The title

Given an array, move the elements of the array k positions to the right, where k is non-negative.

Example 1: input: nums =,2,3,4,5,6,7 [1], k = 3 output:,6,7,1,2,3,4 [5] : spin to the right step 1:,1,2,3,4,5,6 [7] spin to the right step 2: ,7,1,2,3,4,5 [6] to the right rotation step 3:,6,7,1,2,3,4 [5] example 2: input: nums = [- 1-100,3,99], k = 2 output: [13, 3-1-100] : spin to the right step 1: [99,-1,-100,3] 2 steps to the right: [3,99,-1,-100]Copy the code

Analysis of the

1. Move k, k>=0

2. Goal: Put the last K elements first

solution

1. Double array

2.reverse

3.pop+unshift

Solution one: even number group

Train of thought1.take2Three arrays, one for the prefix elements of the rotated array and one for the suffix elements2.Update the array */var rotate = function (nums, k) {
  const preArr = [],
    sufArr = [];
  const len = nums.length;
  If K>len, take the remainder
  k = k % len;

  // preArr holds the prefix element, sufArr holds the suffix element
  for (let i = 0; i < nums.length; i++) {
    if (i < len - k) preArr[i] = nums[i];
    else sufArr[i] = nums[i];
  }

  // Update the original array
  for (let i = 0; i < nums.length; i++) {
    if (i < k) nums[i] = sufArr[i + len - k];
    elsenums[i] = preArr[i - k]; }};/* Complexity time O(n) space O(n) */
Copy the code

Solution two: double pointer

Train of thought1.Use a double pointer to flip the array2.Let's flip the whole array3.Move k, flip the array before k4.The array */ after k is flippedvar rotate = function (nums, k) {
  const len = nums.length;
  // Take the remainder to prevent overbounding
  k = k % len;
  // Use the double pointer to flip
  function reverse(arr, start, end) {
    for (let left = start, right = end; left < right; ) {
      // Swap elements
      consttemp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; }}// Flip the entire array
  reverse(nums, 0, len - 1);
  // Flip the array before k
  reverse(nums, 0, k - 1);
  // Flip the array after k
  reverse(nums, k, len - 1);
};
/* Complexity time O(n) space O(1) */
Copy the code

Method 3:unshift+pop(timeout is for reference only)

Train of thought1.I take k elements2.Put it after */var rotate = function (nums, k) {

  for (let i = 0; i < k; i++) {
    constitem = nums.pop(); nums.unshift(item); }};/* Complexity time O(n^3) space O(1) */
Copy the code

conclusion

This question examines the understanding of flipping an array, which can be done by “flipping” and “adding an extra array.

You can look at a column I share (front-end algorithm) there are more questions about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me a like, thank you very much

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Part of the material in this article comes from the network. If there is infringement, please contact delete, [email protected]