循环有序数组的二分查找

亚马逊面试题:给定一个循环有序数组,形如 [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8] ,在其中查找某个元素。

最简单直接朴素的算法,从头至尾依次遍历,复杂度O(n)。如果只能做到这样的话,就不必再说了。 对于普通的有序数组,通常会采用二分法查找元素,这样复杂度可以降低至O(logN)。但是这个循环的有序数组的最大最小部分在数组中间而不是在头尾,是否还可以采用二分法查找呢? 普通的二分法思路是:在中间取一元素,与要查找的目标元素对比,若中间元素较大,则在左半部继续二分法查找;反之,若中间元素较小,则在右半部继续二分法查找。如下:

/* 
   p is the start index, 
   q is the end index, 
   x is the target data 
*/
int binary_search(int x, int p, int q, int *a) {
    if (p >= q && a[p] != x)
        return -1;

    int m = (p + q) / 2;

    if (a[m] == x)
        return m;

    if (x > a[m])
        p = m + 1;
    else
        q = m - 1;

    return binary_search(x, p, q, a);
}

该算法应用到这个循环数组上的时候,以在数组[9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8]中查找元素 0 为例,第一步取中间第 9 个元素值为 18 :

search: 0        |   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  
----------------------------------------------------------------------------------------------------
p= 0, m= 9, q=19 |   9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,  0,  1,  2,  3,  4,  5,  6,  7,  8,

此时目标元素 0 小于中间元素 19,该如何判断下一步是应该在左半边查找还是在右半边查找呢?仔细观察该数组,在下标9处被分为两个部分,左边为[9, 10, ..., 18],右边为[19, 0, ..., 8]。以目测的结果来看,应该在右半边继续查找,与原始二分法的判断结果恰好相反。原始的算法,只能应用于一个单调递增的数组,而循环数组则将一个单调递增数组变成了两个单调递增数组。第一部取完中点之后,数组被分为两个部分。一般的情况下,一部分必然为单调递增,一部分为非单调递增(含有断点)。很容易想到,如果目标元素在单调递增那一部分,则可继续在此区间查找,此区间内的查找则是原始的二分查找;如果目标元素在非单调递增部分,则又还原成了原问题,只是查找范围缩小了一半。重复这个过程,则可以得到查找结果。

search : 0       |  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  
----------------------------------------------------------------------------------------------------
p= 0, m= 9, q=19 |  9, 10, 11, 12, 13, 14, 15, 16, 18, 18, 19,  0,  1,  2,  3,  4,  5,  6,  7,  8, 
p=10, m=14, q=19 |                                         19,  0,  1,  2,  3,  4,  5,  6,  7,  8, 
p=10, m=11, q=13 |                                         19,  0,  1,  2, 
result: 11

在这个过程中,需要注意几个个问题:

  1. 如何判断一段数组是单调递增呢?在该段数组的头、中间、尾三个位置p,m,q取三个值a[p], a[m], a[q],如果是单调递增则一定满足 a[p] >= a[m] >= a[q],否则则非单调递增。

  2. 判断目标元素下一步所在区间,有几种情况:

    • 当 x > a[m] 时,
      • 右半边是单调递增区间,并且x在此区间内,下一步则可在此右半边区间内查找
      • 右半边是单调递增区间,并且x不在此区间内,下一步在左半边查找
      • 右半边是非单调递增区间,则x必然在此区间内,下一步在右半边查找
    • 当 x < a[m] 时, 同理类似
      • 左半边是单调递增区间,并且x在此区间内,下一步则可在此左半边区间内查找
      • 左半边是单调递增区间,并且x不在此区间内,下一步在右半边查找
      • 左半边是非单调递增区间,则x必然在此区间内,下一步在左半边查找
  3. 判断是否在单调递增部分,只需与区间的另外一头的元素比较一下大小即可知道

样例代码:

#include <stdio.h>

#define N 20
int arr[N] = {9,10,11,12,13,14,15,16,17,18,19,0,1,2,3,4,5,6,7,8};

void print_header(int target) {
    printf("search :%2d %*c | ", target, 5, ' ');
    for (int i = 0; i < N; i++) {
        printf("%2d  ", i);
    }
    printf("\n");
    for (int i = 0; i< N; i++) {
        printf("-----");
    }
    printf("\n");
}

void print_array(int p, int m, int q, int *a) {
    printf("p=%2d, m=%2d, q=%2d |%*c", p, m, q, 4 * p + (p>0?1:0), ' ');
    for (int i = p; i <= q; i++) {
        printf("%2d, ", a[i]);
    }
    printf("\n");
}

/* 非递归方式 */
int search_loop_array(int x, int* a, int length) {
    int p = 0;
    int q = length - 1;

    while ( p <= q ) {
        int m = ( p + q ) / 2;

        print_array(p, m, q, a);

        if ( x == a[m] )
            return m;

        if ( x > a[m] ) {
            int mm = ( m + q ) / 2;
            int increase = (a[m] <= a[mm] && a[mm] <= a[q]);
            if ( ( increase && x <= a[q] ) || ! increase)
                p = m + 1;
            else
                q = m - 1;
        } else {
            int mm = ( p + m ) / 2;
            int increase = a[p] <= a[mm] && a[mm] <= a[m];
            if ( increase && x >= a[p] || !increase) 
                q = m - 1;
            else
                p = m + 1;
        }
    }

    return -1;
}

/* 递归方式 */
int search_loop_array2(int x, int low, int high, int* a) {
    if (low >= high && a[low] != x)
        return -1;

    int m = (low + high) / 2;

    print_array(low, m, high, a);

    if ( x == a[m] )
        return m;

    if ( x > a[m] ) {
        int mm = (m + high) / 2;
        int increase = (a[m] <= a[mm] && a[mm] <= a[high]);

        if ( !increase || (increase && x <= a[high] ) )
            low = m + 1;
        else
            high = m - 1;

    } else {
        int mm = (low + m) / 2;
        int increase = (a[low] <= a[mm] && a[mm] <= a[m]);

        if ( !increase || (increase && x >= a[low] ) )
            high = m - 1;
        else
            low = m + 1;
    }

    return search_loop_array2(x, low, high, a);
}

int main() {

    for (int i = 0; i < N; i++) {
        print_header(i);

        // printf("result: %d\n\n", search_loop_array(i, arr, N));
        printf("result: %d\n\n", search_loop_array2(i, 0, N-1, arr));
    }
    return 0;
}

完。

行列有序矩阵求第K个数

问题:n*n的行列有序的矩阵M,求第K大的数。行列有序是指每行、每列都是有序的。

最直接的办法就是给整个矩阵排序,然后找第K大的数。复杂度是(O(n^2logk))。其实还有更快的办法。

假设行列都是增序。注意到在矩阵的对角线上中任选一点x,右下角的矩阵里面的数都大于或等于x,而这里包含了(x^2)个数。因此,必然可以找到一个位置x,使得 ((x+1)^2\leq n-k\leq x^2) 。 这样K就在 M(x+1, x+1) .. M(x+1, n) 和 M(x+1, x+1) .. M(n, x+1) 以及 x 这三个范围内。

对这个范围内的数字排序,找第K个数字,复杂度是 (O(nlogk))

事实证明,我还是把这个问题想简单了,之前的解法是错的,因为取(a, a)点后,并不能保证a是除左上角矩阵最大的值,左下和右上仍然有可能有比(a, a)小的数字。

后来又想了个办法,做一个队列,伪代码如下:

findSortedMatrix {
    队列置空
    取M(0, 0),入队
    for (int i=0; i < K; i++) {
        队列首元素出队,置为X 坐标为(x, y)
        取元素X的左边和下边的元素“插入”队列,使队列保持有序
    }
}

为了提高插入的速度,可以用堆的结构实现二分查找插入。这样,空间复杂度是(O(k)), 算法复杂度为(O(klogk)),最坏情况是空间(O(n^2)), 时间(O(klogn))。

当然,这仍然不是最快的解法。查了下资料,发现这个问题确实蛮困难,有篇论文研究了这个问题,对于一个(m\times n)的矩阵算法复杂度可以达到(O(n\log2m/n)) ,不过原始论文要砍25刀。

这篇Blog也提到了这个问题,给了个简要的描述。

字节按位逆序

问题:给一个8位的字节,按位逆序。第一反应给了个简单的做法:

unsigned short intreverse_bit(unsigned short int b)
{
    unsigned short int r = 0;
    for (int i=0; i<8; i++) {
        b >> = 1
        r = (r << 1) | (b & 1);
    }
    return r;
}

每次循环,r左移一位,b取最后一位填充到r的最后一位上,这个解答需要做8次循环,32次操作(左移一次,加法一次,右移一次,按位与一次)。很明显还有更好的做法。

unsigned short int reverse_bit(unsigned short int b)
{
    b = b << 4 + b >> 4;    // &11110000, 56781234
    b = (b & 0x33) << 2 + (b & 0xCC) >> 2;    // &11001100, 78563412
    b = (b & 0x55) << 1 + (b & 0xAA) >> 1;    // &10101010, 87654321

    return b;
}

只需13次操作。

Continue reading

编程之美 1.2 中国相帅问题的一个简洁解法

题目意思大概是,象棋棋盘上只有一相一帅,只能在9宫格内移动,且不能对面。要求给出相帅所有的位置的可能性,只能用一个变量。

只用一个变量,第一感是用位操作。给九宫格编个号:

1 2 3
4 5 6
7 8 9

遍历所有的位置,如果 位置编号 mod 3相同,说明在同一列中。按此思路,书中位操作的解法略显繁杂。这里一个简洁的的解法是:

  1 #include
  2
  3 void main()
  4 {
  5     short unsigned int x;
  6
  7     for (x = 0; (x & 0xF0) < 0x90; x += 0x10 ) {
  8         for ( x &= 0xF0; (x & 0x0F) < 9; x++)
  9             if ((x >> 4) % 3 != (x & 0x0F) % 3)
 10                 printf("A = %d, B = %d\n", (x >> 4) + 1, (x & 0x0F) + 1);
 11     }
 12 }

如果不用位操作的话,另外一个解法比较赞:

BYTE i = 81;
while (i--)
{
    if (i / 9 % 3 != i % 9 % 3)
        printf("A = %d, B = %d\n", i / 9 + 1, i % 9 + 1);
}

旋转矩阵

前天在Google Groups的TopLanguge中看到的一个从JavaEye转过来的帖子。本来应该是给大学生做的课后习题,可是看到的坛友给出的C、C++、Python、Java等代码,都是一大堆的if/else要么就是 switch,何其冗长。和楼主给出的那个反例也差不了多少了。 when int i=5; output:

 1  2  3  4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

when int i=6; output:

 1  2  3  4  5  6
20 21 22 23 24  7
19 32 33 34 25  8
18 31 36 35 26  9
17 30 29 28 27 10
16 15 14 13 12 11

This is a simple python program which hate if/else and switch.

MAX = 10
matrix = [[0 for col in range(MAX)] for row in range(MAX)]
(x, y, count, link) = (-1, 0, 1, {1:(1,0,2), 2:(0,1,3), 3:(-1,0,4), 4:(0,-1,1)})
(dx, dy, direct) = link[1]
while count <= MAX*MAX:
    (nx, ny) = (x + dx, y + dy)
    if (0 <= nx < MAX) and (0 <= ny < MAX) and (matrix[ny][nx] == 0):
        matrix[ny][nx] = count
        (x, y, count) = (nx, ny, count + 1)
    else:
        (dx, dy, direct) = link[direct]

for x in range(MAX):
    print matrix[x]