企业网站设计公司,谷歌服务加速 wordpress,衣服搭配网站建设,河南省专业做网站公司这个算法采用了荷兰国旗问题#xff08;Dutch National Flag Problem#xff09;的解法思想#xff0c;用三个指针将数组中的元素分为三个区域#xff0c;并且对这些区域进行动态调整#xff0c;达到排序的目的。
算法思想#xff1a; 三个指针#xff1a; low 指针表示… 这个算法采用了荷兰国旗问题Dutch National Flag Problem的解法思想用三个指针将数组中的元素分为三个区域并且对这些区域进行动态调整达到排序的目的。
算法思想 三个指针 low 指针表示当前0应该存放的区域的边界。mid 指针用来遍历数组每次检查当前位置的元素。high 指针表示当前2应该存放的区域的边界。 算法步骤 开始时low 和 mid 都指向数组的开头high 指向数组的末尾。遍历数组当 mid 小于等于 high 时 如果 nums[mid] 0表示当前元素是红色0应该放到数组的前面所以与 low 交换low 和 mid 同时右移一位。如果 nums[mid] 1表示当前元素是白色1不需要移动mid 右移一位。如果 nums[mid] 2表示当前元素是蓝色2应该放到数组的末尾所以与 high 交换并将 high 左移一位而 mid 不动等待交换后的元素检查。 循环结束条件 当 mid 指针超过 high 时说明所有的元素都已经按照红、白、蓝的顺序排列完毕。
关键点
in-place 排序这个算法不需要额外的空间直接在原数组上进行排序。时间复杂度每个元素最多被遍历一次因此时间复杂度是 O(n)其中 n 是数组的长度。空间复杂度由于只使用了常数级别的额外空间空间复杂度为 O(1)。
例子
假设输入数组是 [2,0,2,1,1,0]
初始化 low 0, mid 0, high 5。第一次遍历 nums[mid] 2交换 nums[mid] 和 nums[high]数组变为 [0,0,2,1,1,2]high 左移。第二次遍历 nums[mid] 0交换 nums[mid] 和 nums[low]low 和 mid 右移数组不变。持续遍历并根据上述逻辑调整最终数组为 [0,0,1,1,2,2]排序完成。
这个算法的核心是通过遍历数组动态调整0、1、2的位置保证红色、白色、蓝色按照顺序排列。
java 代码
class Solution {public void sortColors(int[] nums) {int low 0, mid 0, high nums.length - 1;while(mid high) {if(nums[mid] 0) {swap(nums, low, mid);low;mid;} else if(nums[mid] 1) {mid;} else if(nums[mid] 2) {swap(nums, mid, high);high--;}}}private void swap(int[] nums, int start, int end) {int temp nums[start];nums[start] nums[end];nums[end] temp;}
}
