首页 > itarticle > partition array

partition array

admin 11月 11, 2020 0


Partition Array
双指针，begin和end。
在遍历数组的时候，分情况讨论:
1. 如果nums[begin] < k, 不用管，直接begin++
2. 如果nums[begin] >= k, 开始交换，但是交换的时候， 右边的end指针先移动，移动到第一个小于k的数字上
看了别人写的答案，觉得好多了。有点quick sort的思想。begin为第一个nums[begin] >= k的index， end 为第一个nums[end] < k的index，然后swap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
public int (int[] nums, int k) {
    
    if (nums == null || nums.length == 0)
        return 0;
    int begin = 0, end = nums.length - 1;
    while (begin <= end) {
        while (begin <= end && nums[begin] < k) {
            ++begin;
        }
        while (begin <= end && nums[end] >= k)
            --end;

       if (begin <= end)
           swap(nums, begin, end);
    }
    return begin;
}

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

Sort Letters by Case
和上面一题是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
public void sortLetters(char[] chars) {
    
    if (chars == null || chars.length == 0)
        return;
    int ptr1 = 0, ptr2 = chars.length - 1;
    while (ptr1 <= ptr2) {
        while (ptr1 <= ptr2 && Character.isLowerCase(chars[ptr1]))
            ++ptr1;
        while (ptr1 <= ptr2 &&  Character.isUpperCase(chars[ptr2]))
            --ptr2;
        if (ptr1 <= ptr2)
            swap(chars, ptr1, ptr2);
    }
}

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

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能