1. 调整数组使奇数全部都位于偶数前面。

void partition(int* arr, int size) {
    int left = 0, right = 0;
    int tmp;

    while (right < size) {
        if (arr[right] % 2 != 0) {  // odd
            tmp = arr[right];  // swap
            arr[right] = arr[left];
            arr[left] = tmp;
            left++;
            right++;
        }
        else {  // even
            right++;
        }
    }
}

2. 杨氏矩阵

有一个二维数组.
数组的每行从左到右是递增的,每列从上到下是递增的.
在这样的数组中查找一个数字是否存在。
时间复杂度小于O(N);

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ROW 3
#define COL 3

// 查找arr[row][col]元素
int findNumInYangMatrix(int arr[ROW][COL], int findedArr[ROW][COL], int row, int col, int num) {
    int sign;

    if (findedArr[row][col] == 1) {
        return 0;
    }
    else if (col >= COL || row >= ROW) {
        return 0;
    }
    else if (arr[row][col] == num) {
        return 1;
    }
    else {
        findedArr[row][col] = 1;
        sign = findNumInYangMatrix(arr, findedArr, row + 1, col, num);
        return sign ? sign : findNumInYangMatrix(arr, findedArr, row, col + 1, num);
    }
}

int main() {
    int arr[ROW][COL] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
    int findedArr[ROW][COL] = { 0 };  // 用一个数组记录已经查找过的元素,防止重复计算
    printf("%d\n", findNumInYangMatrix(arr, findedArr, 0, 0, 10));

    system("pause");
    return 0;
}
Last modification:November 10th, 2019 at 10:20 am