劍指offer之二維數(shù)組中查找

1 問題

二維數(shù)組中查找：

在一個二維數(shù)組鐘，每一行都按照從左到右遞增得順序排列，每一列
都按照從上往下得遞增排列，請完成一個函數(shù)，輸入這樣得一個二維數(shù)組和一個
整數(shù)，判斷數(shù)組是否含有該整數(shù)

列如：

1  2  8   9
2  4  9   12
4  7  10  13
6  8  11  15

 
2 分析

比如我們要找數(shù)字7， 我們先從右上角開始分析，如果要找的值比9小，我們在把列向左移動，然后再去把列向左移動，再去找8，然后發(fā)現(xiàn)還是比8小，我們依然向左移動，我們再去找到2，然后發(fā)現(xiàn)比2大，我們再把行向下移動，找到4，然后我們發(fā)現(xiàn)4還是比7小，我們再把行往下移動，以此類推，然后我們發(fā)現(xiàn)找到了7.


 
3 代碼實現(xiàn)

    #include <stdio.h>
     
    int find(int a[][4], int rows, int  columns, int value)
    {
        if (a == NULL || rows <= 0 || columns <= 0)
        {
            return -1;
        }
        int i = 0;
        int j = columns - 1;
        while (i < rows 0 && j >= 0)
        {
            if (a[i][j] == value)
            {
                return 0;   
            }
            else if (a[i][j] > value)
            {
                j--;
            }
            else
            {
                i++;
            }
        }
        return -1;
    }
     
    int find1(int a[][4], int rows, int  columns, int value)
    {
        for (int i = 0; i < rows;)
        {
            for (int j = columns - 1; j >=0;)
            {
                if (a[i][j] == value)
                {
                    return 0;   
                }
                else if (a[i][j] > value)
                {
                    j--;
                }
                else
                {
                    i++;
                }
            }
        }
        return -1;   
    }
    int main()
    {
        int a[4][4] = {{1, 2, 8, 9}, {2, 4, 9 , 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        int result1 = find(a, 4, 4, 11);
        int result2 = find(a, 4, 4, 3);
        printf("result1 is %d\n", result1);
        printf("result2 is %d\n", result2);
        int result3 = find(a, 4, 4, 11);
        int result4 = find(a, 4, 4, 3);
        printf("result3 is %d\n", result3);
        printf("result4 is %d\n", result4);
        return 0;
    }


4 運行結(jié)果

    result1 is 0
    result2 is -1
    result3 is 0
    result4 is -1

 
5 總結(jié)

既然我們分析過程會發(fā)現(xiàn)行和列都會變，那么我們肯定需要用2個變量去表示行和列，那么我們肯定要找到便利得終止條件，就是變量行不能大于數(shù)組真正得行，然后列的話不能小于0，這個問題我一開始用得2個for，然后for里面寫了i和j的變化，后面發(fā)現(xiàn)不好理解，然后如果以后我們只要涉及到for里面得i和j更加實際情況需要動態(tài)變化的，我們就不要用2個for循環(huán)了，我們直接用

while(終止條件) ｛i變化，j變化｝里面改變i和j的值，也就是在while循環(huán)里面直接操刀i和j，一定要記住。


 


作者：chen.yu
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進階人工智能(鏈接)