【算法】【数组与矩阵模块】数组的partition调整-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】【数组与矩阵模块】数组的partition调整。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个有序数组，但是存在重复，求调整数组，使得数组的右半部分没有重复元素，且升序，数组的左半部分无需保证有序
如：arr = [0,1,1,2,2,2,2,3,3,4,5,6]
结果为：
arr = [0,1,2,3,4,5,6,1,2,2,2,2,3]
进阶问题
给定一个数组arr，arr中仅存在三种类型的元素，如仅存在0,1,2，调整该数组，使得该数组最终变成
00…0011…11…22…22的形式
如:arr = [0,1,1,2,0,1]
结果为：arr = [0,0,1,1,1,2]

解决方案

原问题：
1、申请两个游标，i1，和i2，i1作为待交换的index，i2作为遍历的index
2、初始化i1找到arr中第一个满足 arr[i1-1] = arr[i1]的位置
3、从i2 = i1+1开始遍历，如果i2满足 arr[i2] != arr[i1],则交换i2和i1的位置,之后i1++，i2++
进阶问题：
1、申请三个游标，l，r，i，l代表左边第一个arr[l]不为0的地方，r代表右边第一个arr[r]不为2的地方
2、从i = l+1开始遍历，如果arr[i]为1，则i++，如果arr[i]为2，则i位置和r位置交换，r–，如果arr[i]为0，则i位置和l位置交换l++
3、知道i位置和r位置相遇为止

进阶问题

代码编写

java语言版本

原问题：
方法一:


   /**
     * 二轮测试：数组的partition调整
     * @param arr
     */
    public static void partionMoveCp1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int cur = 1;
        // 从1位置开始找到需要更换的地方
        while (cur < arr.length && arr[cur] != arr[cur-1]) {
            cur++;
        }
        // 从next开始，找与cur不同的
        int next = cur+1;
        while (next < arr.length) {
            if (arr[next] == arr[cur-1]) {
                next++;
            }else {
                // 不相等,交换
                CommonUtils.swap(arr, next, cur);
                next++;
                cur++;
            }
        }
    }

进阶问题

    /**
     * 二轮测试：012数组排序
     * @param arr
     */
    public static void partitionMoveCp2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int left = 0;
        int right = arr.length-1;
        // left指向第一个不为0的
        while (arr[left] == 0){
            left++;
        }
        // right指向第一个不为2的
        while (arr[right] == 2) {
            right--;
        }
        int cur = left+1;
        // 从left+1开始遍历
        while (cur < right) {
            if (arr[cur] == 2) {
                CommonUtils.swap(arr, cur, right);
                right--;
            }else if (arr[cur] == 0) {
                CommonUtils.swap(arr, cur, left);
                left++;
            }else {
                cur++;
            }
        }
    }



    public static void main(String[] args) {
        int[] ints = {1, 2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 8, 9};
        int[] ints1 = {2, 2, 0, 1, 1, 0, 2};
        partitionMoveCp2(ints1);
        CommonUtils.printArr(ints1);
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这种partition调整考察的就是数组的移动和交换的熟练度，总的来说没有什么特别困难的地方
但是如果这道题提升一个维度，如果4种元素进行排序应该如何玩？
如果是我来做，我可能会将问题转化成3中元素的问题，如何转化？
首先将所有元素遍历一遍，现将要放到最左边或者最右边的元素筛选出来，之后将剩下的元素进行调整，就变成了3中元素的问题。
那么现在如果问题又升级了，如果元素的种类有n中呢？难道我们需要循环n-3次先转化成3个元素的问题吗？
这个时候更多的我可能会考虑提升空间复杂度来降低时间复杂度了，比如hash。。。
如果有空间o（1）的方法希望评论区大神们献计献策~