【算法作业】旋转序列，矩阵二分查找

Uncategorized
1.5k words

问题描述

  1. 有一个序列是某个有序系列围绕着下标为K的元素(0 <= k < length)旋转得到的序列，使数组下标变为 [k], [k+1], …, [n-1], [0], [1], …, [k-1]，如 123456围绕着下标为3的元素旋转得到456123，请为此序列编写元素查找算法，并分析你的算法性能。

  2. 我们学习的二分查找算法是针对一维有序序列的，现假设有一个矩阵，其每一行每一列分别是从左到右、从上到下有序的，请为此矩阵编写元素查找算法，并分析你的算法性能。

解题思路

T1

  1. 方法一

    暴力搜索思路非常简单，只用找到数字1的位置就行，然后将数字1的位置减一就是k，甚至数组都不用，直接在输入的时候过一遍就行了。时间复杂度为O(n)

  2. 方法二

其实这个题目的序列旋转点左边有序，右边有序，且左边所有的数都大于右边的数，我们仍然可以使用了二分查找算法。

首先，定义了一个函数searchInRotatedArray，接受三个参数：nums为旋转有序数组，target为目标元素，length为数组长度。

在函数内部，使用二分查找的思想，在每次循环中找到中间元素mid，然后判断目标元素与中间元素的关系：

  1. 如果中间元素就是目标元素，直接返回中间元素的索引。
  2. 如果左半段是有序的，判断目标元素是否在左半段中：如果目标元素在左半段且在左半段有序范围内，则将查找范围缩小为左半段；否则将查找范围缩小为右半段。
  3. 如果右半段是有序的，判断目标元素是否在右半段中：如果目标元素在右半段且在右半段有序范围内，则将查找范围缩小为右半段；否则将查找范围缩小为左半段。

通过不断缩小查找范围，最终可以找到目标元素的索引位置，或者确定目标元素不存在于数组中。

在主函数main中，定义了一个旋转有序数组nums，目标元素target为1，然后调用searchInRotatedArray函数进行查找。最后根据查找结果输出相应的信息。

这段代码的时间复杂度为O(log n) ，其中n为数组长度。

T2

  1. 方法一:

暴力搜索，两层循环，太简单了所以不写

  1. 方法二:

行列切割的二分查找算法

函数searchMatrix接受五个参数：matrix为行列有序的二维数组，rows和cols分别为矩阵的行数和列数，target为目标元素，x和y为目标元素的行列坐标。

在函数内部，使用两个指针row和col分别表示当前查找的行和列，初始时，row指向第一行，col指向最后一列。

然后，通过循环遍历矩阵，每次比较当前位置的元素与目标元素的大小关系：

  1. 如果当前位置的元素等于目标元素，则将目标元素的行列坐标存储到x和y中，返回true。
  2. 如果当前位置的元素小于目标元素，则将指针row向下移动一行，排除当前行。
  3. 如果当前位置的元素大于目标元素，则将指针col向左移动一列，排除当前列。

通过不断地在行和列上移动，直到找到目标元素或者遍历完整个矩阵，最终确定目标元素是否存在于矩阵中。

在主函数main中，定义了一个行列有序的矩阵matrix，目标元素target为5，然后调用searchMatrix函数进行查找。最后根据查找结果输出相应的信息。

这段代码的时间复杂度为O(rows + cols)，其中rows和cols分别为矩阵的行数和列数，因为每次在行或列上移动时，都会减少一半的查找范围。

  1. 方法三:

将二维矩阵顺时针旋转45度，看成二叉排序树

这是我上课听来的方法，现在补充在这里，就懒得写代码。相信各位观众老爷都能写出来的。

完整代码

T1

  1. 方法一
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #include<iostream>
    using namespace std;
    int main(){
    	int length,ans;
    	cout<<"请输入数组长度：";
    	cin>>length;
    	cout<<"请输入数组：";
    	for(int i=1;i<=length;i++){
    		int x;
    		cin>>x;
    		if(x == 1)
    			ans = i - 1;	
    	}
    	cout<<ans;
    	return 0;
    }
  2. 方法二
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    #include <iostream>
    #include <vector>

    using namespace std;

    int searchInRotatedArray(int nums[], int target, int length) {
        int left = 0;
        int right = length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            // 左半段有序
            if (nums[left] <= nums[mid]) {
                // 判断target是否在左半段
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // 右半段有序
            else {
                // 判断target是否在右半段
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1; // 未找到
    }

    int main() {
        int nums[] = {4, 5, 6, 7, 8, 9, 1, 2, 3, 4};
        int target = 1;
        int length = sizeof(nums) / sizeof(nums[0]);
        int index = searchInRotatedArray(nums, target, length);
        if (index != -1) {
            cout << "元素 " << target << " 在数组中的索引位置为：" << length - index << endl;
        } else {
            cout << "未找到元素 " << target << " 在数组中" << endl;
        }
        return 0;
    }

T2

方法二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>

using namespace std;

// 行列切割二分查找
bool searchMatrix(int matrix[][5], int rows, int cols, int target, int &x,int &y) {
    if (rows == 0 || cols == 0) return false;

    int row = 0;
    int col = cols - 1;

    while (row < rows && col >= 0) {
        if (matrix[row][col] == target) {
        	x = row;
        	y = col;
            return true;
        } else if (matrix[row][col] < target) {
            // 排除当前行
            row++;
        } else {
            // 排除当前列
            col--;
        }
    }

    return false;
}

int main() {
    const int rows = 5;
    const int cols = 5;

    int matrix[rows][cols] = {
        {1, 4, 7, 11, 15},
        {2, 5, 8, 12, 19},
        {3, 6, 9, 16, 22},
        {10, 13, 14, 17, 24},
        {18, 21, 23, 26, 30}
    };
	
    int target = 5;
    int x = 0, y = 0;
    for(int i = 0 ; i < cols; i++){
		for(int j = 0;j < rows; j++) 
			cout<<matrix[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
    if (searchMatrix(matrix, rows, cols, target, x, y)) {
        cout << "元素 " << target << " 存在于矩阵中" << endl;
        cout << "左上角是(0,0),targrt坐标为("<< x << "," << y << ")" <<endl;
    } else {
        cout << "元素 " << target << " 不存在于矩阵中" << endl;
    }

    return 0;
}