面试笔试题 - 续 - TinyZ's Blog

665 字

3 分钟

面试笔试题 - 续

2016-06-04

生活

回顾一下之前的笔试题。URL 地址。

问题：有一个数组 a，有一个变量 n，大于变量 n 的放到数组的前面，小于变量 n 的放到数组的后面（不需要排序）。

解决思路：数组 a 从 0 开始向后遍历，检查到小于 n 的元素 k1，那么从队尾指针 tail 处向前遍历，检查到大于 n 的元素 k2 停止，并 k1 和 k2 互换位置。在从 k1 处继续向后遍历直至 k1 位置大于队尾指针位置（遍历结束）。

测试用例:

1
public static void main(String[] args) {
2
    int[] ary = new int[] { 1,2,3,4,5,6,8,5,2,1,3,9,5};
3
    int n = 5;
4
    sort(ary, n);
5

6
    System.out.println();
7
}

逻辑代码如下:

1
public static void sort(int[] array, int n) {
2
    int tail = array.length - 1;
3
    for (int h = 0; h < array.length; h++) {
4
        if (h > tail){
5
            break;
6
        }
7
        if (array[h] < n) {
8
            for (int k = tail; k >= h; k--) {
9
                tail = k;
10
                if (array[k] >= n) {
11
                    int obj = array[h];
12
                    array[h] = array[k];
13
                    array[k] = obj;
14
                    break;
15
                }
16
            }
17
        }
18
    }
19
}

延伸版本，当 n 改为 n1，n2…nx 数组时如何实现?

晚上洗澡的时候想起了这么一个问题。决定折腾一下解决这个问题。最开始有点钻进死胡同。想通过一次遍历实现相应的拆分功能（效率最高的情况）。感觉情况略微有点复杂。考虑十几分钟后感觉可能需要向效率妥协，转变思路。

解决思路：根据 n1, n2… nx 分隔数组 array，先将 n 的数组从大到小排序。再将分隔问题简化成 x 个拆分 n 的连续小问题。

按照 n1 和其他拆分
在 n1 和其他的分界点为起始点, 按照 n2 和其他拆分
重复步骤 2，直至起始点到达数组终点，退出循环.

算法根据数据的复杂度，时间复杂度最小是(O(n)), 最大是 O(n(n+1)/2)。

1
public static void sortn(int[] array, Integer... ns) {
2
    // 这里的排序保证n的数组是从大到小有序的， 当然可以自己设置，以避免排序的损耗
3
    Arrays.sort(ns, new Comparator<Integer>() {
4
        @Override
5
        public int compare(Integer o1, Integer o2) {
6
            return o2-o1;
7
        }
8
    });
9
    int index = 0;
10
    for (int i = 0; i < ns.length; i++) {
11
        index = sort(array, ns[i], index);
12
        if (index >= array.length) {
13
            break;
14
        }
15
    }
16
}
17

18
public static int sort(int[] array, int n, int index) {
19
    int tail = array.length - 1;
20
    for (int h = index; h < array.length; h++) {
21
        if (h > tail){
22
            break;
23
        }
24
        if (array[h] < n) {
25
            for (int k = tail; k >= h; k--) {
26
                tail = k;
27
                if (array[k] >= n) {
28
                    int obj = array[h];
29
                    array[h] = array[k];
30
                    array[k] = obj;
31
                    break;
32
                }
33
            }
34
        }
35
    }
36
    return tail;
37
}