有序数组的平方

爱被打了一巴掌 2024-04-07 14:25 60阅读 0赞

### 977. 有序数组的平方 ###

> 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

##### 示例 1： #####

> 输入：nums = \[-4,-1,0,3,10\]  
> 输出：\[0,1,9,16,100\]  
> 解释：平方后，数组变为 \[16,1,0,9,100\]  
> 排序后，数组变为 \[0,1,9,16,100\]

##### 示例 2： #####

> 输入：nums = \[-7,-3,2,3,11\]  
> 输出：\[4,9,9,49,121\]

###### 提示： ######

> 1 <= nums.length <= 104  
> \-104 <= nums\[i\] <= 104  
> nums 已按 非递减顺序 排序

class Solution {
        
       public int[] sortedSquares(int[] nums) {
        
            int [] sq_nums;
       	 sq_nums = new int [nums.length];
       	 sq_nums[0] = nums[0]*nums[0];
       	 int i,j;
       	 System.out.println(sq_nums[0]);
       	 
       	 for(i=1; i<nums.length; i++) {
        
       		
       		 for(j=i; j>0; j--) {
        
       			 if(sq_nums[j-1] > nums[i]*nums[i])
       				 sq_nums[j] = sq_nums[j-1];
       			 else
       				 break;
       		 }
       		 sq_nums[j] = nums[i]*nums[i];
       	 }
       	 return sq_nums;
       }
    }

#### 进阶： ####

> 请你设计时间复杂度为 O(n) 的算法解决本问题

import java.util.Arrays;
    
    /**
     * @author RMZH
     *
     */
    public class sq_array {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		int [] nums = {-7,-3,2,3,11};
    		System.out.println(Arrays.toString(nums));
    		System.out.println(Arrays.toString(sortedSquares(nums)));
    	}
    	
    	 public static int[] sortedSquares(int[] nums) {
    		 int [] sq_nums;
    		 sq_nums = new int [nums.length];
    		 sq_nums[0] = nums[0]*nums[0];
    		 int i,j;
    		 System.out.println(sq_nums[0]);
    		 
    		 for(i=1; i<nums.length; i++) {
    			
    			 /**for(j=i; j>0; j--) {
    				 if(sq_nums[j-1] > nums[i]*nums[i])
    					 sq_nums[j] = sq_nums[j-1];
    				 else
    					 break;
    			 }
    			 */
    			 sq_nums[i] = nums[i]*nums[i];
    		 }
    		 Arrays.sort(sq_nums);
    		 return sq_nums;
    	 }
    
    }

来源：力扣（LeetCode）  
链接：[https://leetcode.cn/problems/squares-of-a-sorted-array][https_leetcode.cn_problems_squares-of-a-sorted-array]  
仅供学习参考

[https_leetcode.cn_problems_squares-of-a-sorted-array]: https://leetcode.cn/problems/squares-of-a-sorted-array