旅游网站设计说明书,nodejs做网站容易被攻击吗,页面设计工作内容自述,阿坝网站设计java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 双指针两次遍历2. 三指针 1. 双指针两次遍历
解题思路#…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. 双指针两次遍历2. 三指针 1. 双指针两次遍历
解题思路时间复杂度O( n n n)空间复杂度O( 1 1 1)需要遍历两次数组 第一遍遍历将所有0放到前面第二遍遍历将所有1放在0后面 代码 class Solution {//交换public static void changePosition(int arr[],int i,int j){int temp arr[i];arr[i] arr[j];arr[j] temp;}public void sortColors(int[] nums) {int n nums.length;int left 0;//指向交换位置for(int right 0;rightn;right){//将0换到left位置if(nums[right] 0) changePosition(nums,left,right);}for(int right left;rightn;right){//将1换到left位置if(nums[right] 1) changePosition(nums,left,right);}}
}2. 三指针
解题思路时间复杂度O( n n n)空间复杂度O( 1 1 1)只遍历1次数组 p0指向下一个0需要放置的位置同理p1指向下一个1需要放置的位置我们使用p2指针来进行遍历数组如果发现p2指向的是1就和p1位置交换同时p1当p2指向0时需要和p0交换但是有一种特殊情况 例如0011220,其中1是p0位置2是p1位置0是p2位置此时我们发现p1的位置是超过p0的也就是说此时p1后面一定是1而p0的下一个插入位置就在p1的后面也就是p0比如指向1此时我们要让p0和p2交换位置结果为0001221。我们发现虽然现在p0位置放上了0但是p0原来指向的1却放到了p2位置也就是说我们为了换一个0把1交给了p2.此时就需要p1和p2将这个1要回来因此只要我们p0和p2交换完成后发现p0p1就需要再让p1和p2额外进行一次交换结果为0001122 代码 class Solution {//交换public static void changePosition(int arr[],int i,int j){int temp arr[i];arr[i] arr[j];arr[j] temp;}public void sortColors(int[] nums) {int p0 0;int p1 0;int p2 0;//三快慢指针p2最快p1其次p0最后while(p2nums.length) {//if(nums[p2] 1) changePosition(nums,p1,p2);//如果当前p2指向1则和p1指针交换else if(nums[p2] 0) {//如果当前p2是0changePosition(nums,p0,p2);//和p0交换位置//如果此时p0和p1指向的位置不是同一个也就是p1在p0前面那么说明p0当前位置原来是1//p0和p2交换后也就是将p2位置的0放到了p0位置。而p0原来位置的1放在了p2位置//此时就需要将p2位置的1换给p1.也就是必须p1和p2再次交换if(p0p1) changePosition(nums,p1,p2);p0;p1;//0向前走1就得向前走}p2;}}
}
