Double pointer

[977] The square of an ordered array

Category	Difficulty	Likes	Dislikes
algorithms	Easy (72.54%).	257	–

Given an array of integers, nums, sorted in non-decrement order, return a new array of squares for each number, and ask for non-decrement order as well.

Individual solution

var sortedSquares = function (nums) {
 for (let i in nums) {
        nums[i] = nums[i] * nums[i];
    }
    nums.sort((a, b) = > a - b);
    return nums;
};
Copy the code

through	116 ms	45.8 MB	JavaScript

Analysis of the

The individual solution is the violent solution. Because arrays are sorted in non-decrementing order, you can also try the double-pointer method. Arrays are sorted in non-decrement order, and the maximum value of the squared elements must be at either end. Define the subscripts left and right for the left and right endpoints of the array, and compare the square values of the two endpoints. Insert larger values at the beginning of the new array arr until left=right.

The second solution

var sortedSquares = function (nums) {
let [left, right] = [0, nums.length - 1];
    let arr = [];
    while (left <= right) {
        if (nums[left] * nums[left] < nums[right] * nums[right]) {
            arr.unshift(nums[right] * nums[right]);
            right--;
        } else{ arr.unshift(nums[left] * nums[left]); left++; }}return arr;
};
Copy the code

through	160 ms	44.7 MB	JavaScript

Analysis of the

The time complexity of the algorithm is reduced. Alternatively, you can use the absolute value function math.abs ().

const left = Math.abs(nums[i])
const right = Math.abs(nums[j])
Copy the code

[189] Rotate the array

Category	Difficulty	Likes	Dislikes
algorithms	Medium (45.38%).	1042	–

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

Individual solution

var rotate = function (nums, k) {
while (k > nums.length) {
        k = k - nums.length;
    }
    let arr = nums.splice(nums.length - k, k);
    arr.reverse();
    for (let item of arr) {
        nums.unshift(item);
    }
    return nums;
};
Copy the code

Analysis of the

The individual solution is the violent solution. Consider inverting the array in the first place. For example, nums = [1,2,3,4,5,6,7] and k = 3. Nums = [7,6,5,4,3,2,1]. The array elements need to be moved to the front of the array for easy operation. In this case, the sequence of the k-bit array elements 7,6,5 and the remaining array elements 4,3,2,1 is opposite to the order of the target result, so the two “small arrays” can be reversed again. Tips: Invert an array by introducing a double-pointer method to swap each element: Define a subscript at the beginning and end of the array, and define an intermediate value temp to store the value of the last element for easy swapping. Write a separate inversion of the array function, call three times, more concise and convenient. If k is larger than the length of the array, it’s essentially moving the length of the remaining digits after the element has been moved by a number of lengths.

The second solution

var rotate = function (nums, k) {
while (k > nums.length) {
        k = k - nums.length;
    }
    const reverse = (arr, start, end) = > {
        while (start < end) {
            let temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
    return nums;
};
Copy the code

through	96 ms	44.9 MB	JavaScript