The profile

Double pointer is a common algorithm idea, which is often used when iterating over a set of numbers. Double pointer mainly has two algorithm techniques: 1, fast and slow pointer (such as the LeetCode advanced combat fast and slow pointer), using the relative position relationship determined by the pointer, the fast pointer reaches the boundary first to search; Two Pointers are traversed from front to back and from back to front respectively, which is exactly what this article describes.

The original problem

977. Squares of a Sorted Array (Easy)

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [4, 1,0,3,10] Output:,1,9,16,100 [0] Example 2:

Input: [-7,-3,2,3,11] Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A is sorted in non-decreasing order.

977. Square of an ordered array

Given an array of integers A sorted in non-descending order, return A new array of the squares of each number, also sorted in non-descending order.

Example 1:

Input: [-4,-1,0,3,10] output: [0,1,9,16,100] example 2:

Input: [-7,-3,2,3,11] output: [4,9,9,49,121]

Tip:

1 <= A.length <= 10000-10000 <= A[I] <= 10000 A has been sorted in non-descending order.

  • Classification: double pointer

Analyze && thinking

Arrays are in non-decreasing order. Both negative and non-negative numbers may exist in arrays. Negative numbers square from left to right (absolute value) and positive numbers square from right to left (absolute value) in the array. Therefore, dual Pointers are used to compare and exchange from left to right and right to left.

Pseudo code

1, create an int array of the same size as the input. 2, declare two pointer subscripts: left to right pointer and right to left pointer; 3,forI. If the absolute value of a positive number is larger from right to left, the square of the larger absolute value is placed at the end of the array, and the left pointer is moved one bit from right to left; Ii. If the absolute value of a non-positive number is larger from left to right, place the number with the larger absolute value at the end of the array and move the pointer right one bit from left to right; 4. At the end of the loop, return the ordered array of the squares of the new array;Copy the code

Coding practices

    public int[] sortedSquares(int[] A) {
        int n = A.length;
        int[] result = new int[n];
        int i = 0, j = n - 1;
        for (int p = n - 1; p >= 0; p--) {
            if (Math.abs(A[i]) > Math.abs(A[j])) {
                result[p] = A[i] * A[i++];
            } else{ result[p] = A[j] * A[j--]; }}return result;
    }
Copy the code

conclusion

This paper introduces the use of the more classical two-way pointer pointer, relatively simple but more representative suitable for basic algorithm entry. In fact, bidirectional Pointers show up in a lot of classic algorithm ideas, such as quicksort. Finally, if you find this article helpful, you might as well pay attention to walk a wave ~