Preface explains

Algorithm learning, daily brush problem record.

Subject to connect

The square of an ordered array

The subject content

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.

Example 1:

Input: nums = [-4,-1,0,3,10]

Output:,1,9,16,100 [0]

[16,1,0,9,100]

After sorting, the array becomes [0,1,9,16,100]

Example 2:

Input: nums = [-7,-3,2,3,11]

Output:,9,9,49,121 [4]

Tip:

1 <= nums.length <= 10^4

-10^4 <= nums[i] <= 10^4

Nums have been sorted in non-descending order

Advanced:

Please design an algorithm with time complexity of O(n) to solve this problem

The analysis process

Use double pointer solution.

The left pointer starts on the left side of the array, and the right pointer starts on the right side of the array. The two Pointers move from both ends of the array to the middle until they are equal, ending the loop.

On each loop, the results array takes only the larger number and moves the pointer to the middle one bit. Then the results array takes the smaller number and moves the pointer to the middle one bit.

Even though the left and right Pointers are moved to the middle at the same time, the pos cursor is moved twice, so the results array is exactly the same length as nums.

Because nums has a maximum value on both sides and gets smaller and smaller as you go in, the results array is constructed from back to front, which happens to be a non-decrement array.

To solve the code

Class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length; Results int[] results = new int[n]; For (int I = 0, j = n - 1, pos = n - 1, pos = n - 1; i <= j;) {if (nums[I] * nums[I] > nums[j] * nums[j]) {if (nums[I] * nums[I] > nums[j] * nums[j]) {if (nums[I] * nums[I] > nums[j] * nums[j]) { Results [pos] = nums[I] * nums[I]; ++i; } else {{result [pos] = nums[j] * nums[j];} else {result [pos] = nums[j] * nums[j]; --j; } --pos; } return results; }}Copy the code

Submit the results

Execution time was 1ms, beating 100.00% of users in time, memory consumption was 40.2MB, and space consumption was 57.04% of users.

The original link

The square of ordered arrays