百度大全网站,宁波网站建设设计制作公司,wordpress模板打开慢,做门用什么网站好java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 时间复杂度 空间复杂度 O(n * l o g 2 n log_2{n} log2…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 时间复杂度 空间复杂度 O(n * l o g 2 n log_2{n} log2n)/kbd2. 时间复杂度O(n)空间复杂度O(1) 1. 时间复杂度 空间复杂度 O(n * l o g 2 n log_2{n} log2n)
解题思路 最直接的想法就是先算出每个元素的平方和然后排序所以排序的效率就是这个算法的效率。那么目前综合性能比最好实现也简单的就是快速排序算法它的时间和空间复杂度为O(n * l o g 2 n log_2{n} log2n) 快速排序https://blog.csdn.net/grd_java/article/details/135671368
代码:时间复杂度O(n * l o g 2 n log_2{n} log2n).空间复杂度O(n * l o g 2 n log_2{n} log2n) class Solution {public int[] sortedSquares(int[] nums) {for (int i 0; i nums.length; i) {nums[i] (int)Math.pow(nums[i],2.0);}
// quickSort(nums);Arrays.sort(nums);return nums;}/**快速排序不稳定时间复杂度O(n * logn) 空间复杂度O(n*logn)* 这里是快排入口*/public void quickSort(int arr[]){quickSort(arr,0,arr.length-1);}/*** 递归主要用于分割左右两个表*/public void quickSort(int arr[],int low,int high){if(lowhigh){//如果左指针超过右指针表示本次比较完成//快速排序每一趟都会确定一个元素的最终位置用pivot表示pivot是枢纽的意思int pivotPosition quickSortPartition(arr, low, high);//由pivot为分界点分成左右两个表quickSort(arr,low,pivotPosition-1);//左表排序quickSort(arr,pivotPosition1,high);//右表排序}}/*** 这里是每一趟的快速排序代码指定一个元素作为枢纽pivot然后以它为中心小的元素放在它左边大的放在它右边*/public int quickSortPartition(int arr[],int low,int high){int pivot arr[low];//指定枢纽while (lowhigh){while(lowhigh arr[high]pivot) --high;//从右边找到比枢纽小的arr[low] arr[high];//放在左边while(lowhigh arr[low]pivot) low;//从左找到比枢纽大的arr[high] arr[low];//放在右边}arr[low] pivot;//最终将枢纽放到它最终的位置return low;//最终low指向枢纽最终位置}
}2. 时间复杂度O(n)空间复杂度O(1) 其实直接用排序算法有些太奢侈了而上面快速排序主要用双指针的思想。那么我们直接用双指针做这道题是不是更好呢 代码:时间复杂度O(n).空间复杂度O(1) class Solution {public int[] sortedSquares(int[] nums) {int n nums.length;//数组长度int low 0, high n -1;//左右指针int position n-1;//答案数组的指针从后向前依次指向插入元素的位置int[] answer new int[n];//每次都将较大值从后向前插入position指向的位置while(high low){int leftPow nums[low]*nums[low];//获取边的平方和int rightPow nums[high] * nums[high];//获取右边的平方和//将较大的插入answer数组并移动指针if(leftPow rightPow) {answer[position] leftPow; low;}//左边的插入answer左指针向右移else {answer[position] rightPow; high--;}//右边元素插入answer右指针向左移动position --;//指向下一个插入位置从后往前依次插入}return answer;}
}
