java数据结构与算法刷题-----LeetCode75. 颜色分类

本文主要是介绍java数据结构与算法刷题-----LeetCode75. 颜色分类，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846

1. 双指针两次遍历

解题思路：时间复杂度O($n$)，空间复杂度O($1$)，需要遍历两次数组

1. 第一遍遍历，将所有0放到前面
2. 第二遍遍历，将所有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;right<n;right++){//将0换到left位置if(nums[right] == 0) changePosition(nums,left++,right);}for(int right = left;right<n;right++){//将1换到left位置if(nums[right] == 1) changePosition(nums,left++,right);}}
}

2. 三指针

解题思路：时间复杂度O($n$)，空间复杂度O($1$)，只遍历1次数组

1. p0指向下一个0需要放置的位置，同理p1指向下一个1需要放置的位置
2. 我们使用p2指针来进行遍历数组，如果发现p2指向的是1就和p1位置交换，同时p1++
3. 当p2指向0时，需要和p0交换，但是有一种特殊情况

1. 例如0011220,其中1是p0位置，2是p1位置，0是p2位置
2. 此时，我们发现p1的位置是超过p0的，也就是说，此时p1后面一定是1，而p0的下一个插入位置，就在p1的后面，也就是p0比如指向1
3. 此时我们要让p0和p2交换位置，结果为0001221。我们发现，虽然现在p0位置放上了0，但是p0原来指向的1，却放到了p2位置
4. 也就是说，我们为了换一个0，把1交给了p2.此时就需要p1和p2将这个1要回来
5. 因此只要我们p0和p2交换完成后，发现p0<p1，就需要再让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(p2<nums.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(p0<p1) changePosition(nums,p1,p2);p0++;p1++;//0向前走，1就得向前走}p2++;}}
}

这篇关于java数据结构与算法刷题-----LeetCode75. 颜色分类的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---