Welcome everyone

算法回马枪 荷兰国旗

算法和数据结构 汪明鑫 224浏览 2评论

何谓荷兰国旗:

现有红、白、蓝三个不同颜色的小球,乱序
排列在一起,请重新排列这些小球,使得红
白蓝三色的同颜色的球在一起。这个问题之
所以叫荷兰国旗,是因为我们可以将红白蓝
三色小球想象成条状物,有序排列后正好组
成荷兰国旗。

 

问题转化:

一个数组a,输入一个数n,请把小于n的数放在数组的左边,等于n的数放在数组的中间,大于n的数放在数组的右边。
算法回马枪 荷兰国旗 算法回马枪 荷兰国旗

 

 public static int[] partition(int []a,int low,int high,int n){
        int i=low-1;     //小于n的区域的边界指针
        int j=high+1;    //大于n的区域的边界指针
        int temp = low;  //遍历指针的出发点

        while(temp<j){   //temp与相遇,结束
            if(a[temp]<n){
                i++;      //小于n的区域的边界指针+1;
                swap(a,i,temp);
                temp++;   //temp指针后移
            }
            else if (a[temp] == n){
                temp++;   //temp指针后移
            }
            else{   //a[temp] > n
                j--;     //大于n的区域的边界指针-1;
                swap(a,temp,j);

            }
        }
        return  new int[] { less + 1, more - 1 };   //返回等于区域
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String []args){
        int []a={1,2,6,7,2,13,4};
        partition(a,0,6,6);
        for(int num: a){
            System.out.print(num+" ");
        }

    }

 

转载请注明:汪明鑫的个人博客 » 算法回马枪 荷兰国旗

喜欢 (0)

说点什么

2 评论 在 "算法回马枪 荷兰国旗"

提醒
avatar
排序:   最新 | 最旧 | 得票最多
lihao
游客

菜逼,抠脚,哈哈哈哈

wpDiscuz