算法初级——荷兰国旗问题

荷兰国旗问题
给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.Arrays;
/**
 * @author sky
 *给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边。
 *要求额外空间复杂度O(1),时间复杂度O(N)
 */
public class 荷兰国旗问题 {
    //算法核心代码:
    public static int[] partition(int[] a,int l,int r,int num) {
        int less = l - 1;
        int more = r + 1;
        int cur = l;
        while(cur < more) {
            if(a[cur] < num) {
                swap(a,++less,cur++);
            }else if(a[cur] > num) {
                swap(a,--more,cur);
            }else {
                cur++;
            }
        }
        return new int [] {less+1,more-1};
    }
   
    //交换代码
    private static void swap(int[] a, int less, int cur) {
        int temp = a[less];
        a[less] = a[cur];
        a[cur] = temp;     
    }
   
    public static int[] generateArray() {  
        int[] arr = new int[10];  
        for (int i = 0; i < arr.length; i++) {  
            arr[i] = (int) (Math.random() * 3);  
        }  
        return arr;  
    }  

    public static void main(String[] args) {
        int[] test = generateArray();//产生一个随机数组  
        System.out.println(Arrays.toString(test));//打印数组
        int[] res = partition(test, 0, test.length - 1, 1);//数组,起始位置,终止位置  
        System.out.println(Arrays.toString(test));
        System.out.println(res[0]);//返回的是等于num的数组的起始位置和终止位置  
        System.out.println(res[1]);  

    }

}
0 条评论
发表一条评论