溧阳做网站哪家好,扁平化网站设计,网站宣传语,利用模板建网站LeetCode977——有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求新数组也按 非递减顺序 排序。
输入#xff1a;nums [-4,-1,0,3,10] 输出#xff1a;[0,1,9,16,100] 解释#xff1a;平方后返回 每个数字的平方 组成的新数组要求新数组也按 非递减顺序 排序。
输入nums [-4,-1,0,3,10] 输出[0,1,9,16,100] 解释平方后数组变为 [16,1,0,9,100] 排序后数组变为 [0,1,9,16,100]
输入nums [-7,-3,2,3,11] 输出[4,9,9,49,121]
1.暴力解
首先对原来的数组进行求平方操作再选用一种排序算法对平方后的数组进行排序。 空间复杂度为O(1),时间复杂度取决于你采用的排序算法。 public static int[] sortedSquares(int[] arr){for (int i 0; i arr.length; i) {arr[i] arr[i]*arr[i];}//选择排序O(N2)的时间复杂度 暴力解insertSort(arr);return arr;}//选择排序public static void selectSort(int[] arr){for (int i 0; i arr.length; i) {int k i;for (int j i1; j arr.length; j) {if (arr[j]arr[k]){k j;}}int temp arr[i];arr[i] arr[k];arr[k] temp;}}2.双指针法
在平方后的数组首尾分别放置指针因为数组可能会存在负数且数组 非递减顺序 所以平方后的最大值必定在首尾中选取。
如果i的值大于j将i存入新数组的最后一位并执行 i k–如果j的值大于i将j存入新数组的最后一位并执行j-- k–这样下来 newArr便为有序的了。 时间复杂度为O(N)空间复杂度为O(N)相对于暴力解法时间复杂度更低以空间换时间。
public static int[] sortedSquares(int[] arr){//空间 换时间 创建一个新数组int[] newArr new int[arr.length];//平方存入原来的数组for (int i 0; i arr.length; i) {arr[i] arr[i]*arr[i];}//i j 分别指向平方后的数组的首尾 因为最大值 肯定在首尾/*i——————0—————————j 如果i的值大于j 将i存入新数组的最后一位 i k--如果j的值大于i 将j存入新数组的最后一位 j-- k--这样下来 newArr便为有序的了*/int i 0;int j arr.length-1;int k newArr.length-1;while (ij){if (arr[i]arr[j]){newArr[k--] arr[i];}else {newArr[k--] arr[j--];}}return newArr;}Tips双指针的思想还是很重要的有兴趣的小伙伴可以去LeetCode27看一下巩固一下双指针的思想。
仅供学习使用
