建站平台免代码,wordpress主机搭建,公司找网站做宣传做账,广西住房城乡建设厅网站首页目录
1、题目介绍
2、解题思路
2.1、冒泡排序暴力破解
2.2、快速排序的子过程partition
2.2.1、详细过程描述
2.2.2、代码描述 1、题目介绍
原题链接#xff1a;75. 颜色分类 - 力扣#xff08;LeetCode#xff09; 示例 1#xff1a; 输入#xff1a;nums [2,0,2…
目录
1、题目介绍
2、解题思路
2.1、冒泡排序暴力破解
2.2、快速排序的子过程partition
2.2.1、详细过程描述
2.2.2、代码描述 1、题目介绍
原题链接75. 颜色分类 - 力扣LeetCode 示例 1 输入nums [2,0,2,1,1,0] 输出[0,0,1,1,2,2] 示例 2 输入nums [2,0,1] 输出[0,1,2] 提示
n nums.length1 n 300nums[i] 为 0、1 或 2
2、解题思路 根据题目的意思简单来说就是将数组里的数据按照0、1、2的顺序排列。 如果只是要求排序其实投机取巧的方式很多比如直接使用冒泡排序也能完成此题。 2.1、冒泡排序暴力破解
void sortColors(int* nums, int sz) {int i 0;int j 0;for (i 0; i sz - 1; i){for (j 0; j sz - 1 - i; j){if (nums[j] nums[j 1]){int tmp nums[j];nums[j] nums[j 1];nums[j 1] tmp;}}}
} 冒泡排序时间复杂度为O(n^2)空间复杂度为O(1 2.2、快速排序的子过程partition 但是根据题目的难度标识为中等很明显这道题不是在考察冒泡排序的。 该题的难点在于如何原地遍历的情况下使得时间复杂度为O(n)空间复杂度为O(1)。即仅使用常数空间的一趟扫描算法。 而这里就用到了快速排序的子过程partitionpartition能够通过一次遍历将所有元素按照标志数进行划分小于放标志数左边大于放标志数右边。 首先这里有个数组规定小num的值放在左侧大于num的值放在右侧而等于num的值放在中间下面进行partition过程讲解。 首先蓝色方框是小于num的区域橙色方框是大于num的区域i从0开始循环遍历。 规则 当arr[ i ]小于num时arr[ i ]与小于区域的下一个元素交换位置然后小于区域向右移动一位i。当arr[ i ]等于num时i。当arr[ i ]大于num时arr[ i ]与大于区域的上一个元素交换位置然后大于区域向左移动一位此时i不自增。 2.2.1、详细过程描述 首先arr[ i ] 等于3小于5 【执行规则1】3与小于区域的下一位元素交换位置而此时小于区域的下一个元素就是3因此交换其实已经完成了。然后小于区域向右移动一位i。 此时arr[ i ] 等于5 【执行规则2】直接 i。 此时arr[ i ] 等于6大于5 【执行规则3】3与大于区域的上一位元素交换位置于是6和8交换位置。然后大于区域向左移动一位。 此时arr[ i ] 等于8大于5 【执行规则3】8与大于区域的上一位元素交换位置于是8和第二个5交换位置。然后大于区域向左移动一位。 此时arr[ i ] 等于5 【执行规则2】直接 i。 此时arr[ i ] 等于7大于5 【执行规则3】7与大于区域的上一位元素交换位置于是7和第二个3交换位置。然后大于区域向左移动一位。 此时arr[ i ] 等于3小于5 【执行规则1】3与小于区域的下一位元素交换位置于是第一个5和第二个3交换位置。然后小于区域向右移动一位i。 此时arr[ i ] 等于4小于5 【执行规则1】4与小于区域的下一位元素交换位置于是第一个5和4交换位置。然后小于区域向右移动一位i。 此时i遇到了大于区域了就停止执行此时数组中的值就变成了左边小右边大中间等于。 2.2.2、代码描述 按照快速排序的子过程partition的方法改造代码 使标志数为1然后将小于1的放左边大于1的放右边既完成排序。 void sortColors(int* nums, int numsSize){int signal 1; //标志数int i 0;int left -1; //left为下标是小于区域的右边界刚开始还未进入数组因此为-1int right numsSize; //right为下标是大于区域的左边界刚开始还未进入数组因此为numsSizewhile(iright) //当i遇上大于区域时停止循环此时就完成了排序{if(nums[i] signal) //当nums[i]小于标志数{int tmp nums[left1]; //交换小于区域的下一个元素nums[left1] nums[i];nums[i] tmp;left;i;}else if(nums[i] signal) //当nums[i]大于标志数{int tmp nums[right-1]; //交换大于区域的上一个元素nums[right-1] nums[i];nums[i] tmp;right--;}else{i; //等于时直接i}}
} 快速排序的子过程partition时间复杂度为O(n^2)空间复杂度为O(1 如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
