[Leetcode][第977题][JAVA][有序数组的平方][排序][双指针]

悠悠 2022-12-15 12:43 99阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

###### 1. 排序 ######

平方后排序 没有使用排序的特性  
**时间复杂度：O(NlogN) 空间复杂度：O(1)**

class Solution { 
        public int[] sortedSquares(int[] A) { 
            int[] ans = new int[A.length];
            for (int i = 0; i < A.length; ++i) { 
                ans[i] = A[i] * A[i];
            }
            Arrays.sort(ans);
            return ans;
        }
    }

###### 2. 双指针 后插法 ######

使用两个指针分别指向位置 00 和 n-1n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。  
**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public int[] sortedSquares(int[] A) { 
            int n = A.length;
            int[] ans = new int[n];
            for (int i = 0, j = n - 1, pos = n - 1; i <= j;) { 
                if (A[i] * A[i] > A[j] * A[j]) { 
                    ans[pos] = A[i] * A[i];
                    ++i;
                } else { 
                    ans[pos] = A[j] * A[j];
                    --j;
                }
                --pos;
            }
            return ans;
        }
    }

#### 【总结】 ####

###### 1. 后插法 往往实现简单 边界条件简单 ######

###### 2.双指针算法大扫荡 ######

单串单向：30，71，76，1508  
单串双向：11，246，905，922，977  
双串单向：392，524，844，925，408  
单串三指针：75，243，245，930

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/f0b6971395d04a80b376061104386553.png