荷兰国旗问题

荷兰国旗问题

问题描述 给定一个数组arr,和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N) 解决思路

1 当前数<目标 当前数和 <区的下一个交换 <区 向右扩 当前数跳下一个2 当前数=目标 当前数直接跳下一个3 当前数>目标 当前数和 >区前一个交换 <区左扩 当前数不变

方法如下

/** * * 1 当前数<目标 当前数和 <区的下一个交换 <区 向右扩 当前数跳下一个 * 2 当前数=目标 当前数直接跳下一个 * 3 当前数>目标 当前数和 >区前一个交换 <区左扩 当前数不变 * * * */ //荷兰国旗 问题 //给定一个数组arr,和一个数num，请把小于num的数放在数组的左边， // 等于num的数放在数组的中间， //大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N) //返回值是一个数组 // arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值 // arr[R] public static int[] netherlandsFlag(int[] arr, int L, int R) { if (L > R) { // L...R L>R return new int[] { -1, -1 }; } if (L == R) { return new int[] { L, R }; } //定义小于等于区 int less = L - 1; // < 区 右边界 //定义大于等于区 //先 int more = R; // > 区 左边界 int index = L; //三种情况进行讨论 while (index < more) { // 当前位置，不能和 >区的左边界撞上 //当相等的时候 就前进 if (arr[index] == arr[R]) { index++; } else if (arr[index] < arr[R]) { //小于最右边的值 //当前值和小于区的下一位交换 小于区向右扩 小于区标志跳到下一位// swap(arr, less + 1, index);// less++;// index++; swap(arr, index++, ++less); } else { // > //当前值和大于区的上一位交换 大于区扩增 swap(arr, index, --more); } } // swap(arr, more, R); // <[R] =[R] >[R] return new int[] { less + 1, more }; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。