当前位置: 首页> 财经> 金融 > 星辰业务自助下单平台_广州网站建设功能_软文营销模板_cps广告联盟平台

星辰业务自助下单平台_广州网站建设功能_软文营销模板_cps广告联盟平台

时间:2025/7/8 22:47:37来源:https://blog.csdn.net/visitorcsdn/article/details/145862126 浏览次数:0次
星辰业务自助下单平台_广州网站建设功能_软文营销模板_cps广告联盟平台

双指针,滑动窗口,排序。

题目

简单做法,单指针,一直遍历,先排小再排大。找到是0的与指针指的位置做交换,交换后指针在这个位置的任务就结束了,接着去定住下一个,然后依次遍历完一趟后找到所有的0,接着下一个数,从这个指针的位置开始一直在后面,找到所有的1做交换,依次重复,然后剩下的就是2了。

时间复杂度: O(n),空间复杂度: O(1)。

class Solution {public void sortColors(int[] nums) {int n = nums.length;int p0 = 0, p1 = 0;for (int i = 0; i < n; ++i) {if (nums[i] == 1) {int temp = nums[i];nums[i] = nums[p1];nums[p1] = temp;++p1;} else if (nums[i] == 0) {int temp = nums[i];nums[i] = nums[p0];nums[p0] = temp;if (p0 < p1) {temp = nums[i];nums[i] = nums[p1];nums[p1] = temp;}++p0;++p1;}}}
}

也可以用hashmap去存每个颜色对应的次数,接着用一个指针去进行填充数组。

时间复杂度: O(n),空间复杂度: O(1)。

class Solution {public void sortColors(int[] nums) {// 创建一个 HashMap 来存储每个颜色(数字)的频率HashMap<Integer, Integer> map = new HashMap<>();// 遍历数组 nums,将每个颜色出现的频次记录到 HashMap 中for (int i = 0; i < nums.length; i++) {map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);}// 使用指针来填充数组int index = 0;// 按照颜色的顺序填充数组for (int color = 0; color <= 2; color++) {int count = map.getOrDefault(color, 0);  // 获取当前颜色的出现次数for (int i = 0; i < count; i++) {nums[index++] = color;  // 从当前位置填充当前颜色}}
}
}

以上都是遍历了两趟,那使用一趟时就得用双指针或三指针了。用一个指针从头扫到尾端做一趟遍历,找到对应的数与左右指针交换,找到一的时候,则直接将遍历的指针移动。用一个指针记录低的数,完成任务后右移,用一个指针记录高的数,完成任务后左移。用这个遍历的指针依次交换就可以排好序了。

时间复杂度: O(n),空间复杂度: O(1)。

class Solution {public void sortColors(int[] nums) {int low = 0, mid = 0, high = nums.length - 1;while (mid <= high) {if (nums[mid] == 0) {// 当前数字是0,交换 low 和 midswap(nums, low++, mid++);} else if (nums[mid] == 1) {// 当前数字是1,继续往后移mid++;} else {// 当前数字是2,交换 mid 和 highswap(nums, mid, high--);}}}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}
class Solution {public void sortColors(int[] nums) {int n = nums.length;int p0 = 0, p2 = n - 1;for (int i = 0; i <= p2; ++i) {while (i <= p2 && nums[i] == 2) {swap(nums,i,p2--);}if (nums[i] == 0) {swap(nums,i,p0++);}}}private void swap(int[] nums,int i,int j){int tmp=nums[i];nums[i]=nums[j];nums[j]=tmp;}
}

 本题对准指针做交换可得到较好的排序,然后也要看一下交换后的情况是不是还需再排。

 

 

关键字:星辰业务自助下单平台_广州网站建设功能_软文营销模板_cps广告联盟平台

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: