1.4.19

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

问题类似于 POJ 上的一道题「滑雪」,从数值较高的一侧向周围数值较小的一侧移动,直到到达「山谷」(局部最小)。

首先在中间行搜索最小值,再将最小值与其上下两个元素比较,如果不满足题意,则“滑向”较小的一侧,矩阵被分为了两半(上下两侧)。

在较小的一侧,找到中间列的最小值,再将最小值与其左右两个元素比较,如果不满足题意,类似的移动到较小的一侧(左右两侧)。

现在查找范围缩小到了原来矩阵的四分之一,递归的进行上述操作,最后可以得到答案。

每次查找最小值都是对行/列进行遍历,遍历耗时和 N 成正比。

代码

using System;

namespace _1._4._19
{
    /*
     * 1.4.19
     * 
     * 矩阵的局部最小元素。
     * 给定一个含有 N^2 个不同整数的 N×N 数组 a[]。
     * 设计一个运行时间和 N 成正比的算法来找出一个局部最小元素:
     * 满足 a[i][j] < a[i+1][j]、a[i][j] < a[i][j+1]、a[i][j] < a[i-1][j] 以及 a[i][j] < a[i][j-1] 的索引 i 和 j。
     * 程序运行时间在最坏情况下应该和 N 成正比。
     * 
     */
    class Program
    {
        // 先查找 N/2 行中的最小元素,并令其与上下元素比较,
        // 如果不满足题意,则向相邻的最小元素靠近再次查找
        static void Main(string[] args)
        {
            int[,] matrix = new int[5, 5] 
            { 
                { 26, 3, 4 , 10, 11 }, 
                { 5, 1, 6, 12, 13 }, 
                { 7, 8, 9 , 14, 15 }, 
                { 16, 17, 18, 27, 20 }, 
                { 21, 22, 23, 24, 25 }
            };
            Console.WriteLine(MinimumRow(matrix, 0, 5, 0, 5));
        }

        /// <summary>
        /// 在矩阵中间行查找局部最小。
        /// </summary>
        /// <param name="matrix">矩阵。</param>
        /// <param name="rowStart">实际查找范围的行起始。</param>
        /// <param name="rowLength">实际查找范围的行结尾。</param>
        /// <param name="colStart">实际查找范围的列起始。</param>
        /// <param name="colLength">实际查找范围的列结尾。</param>
        /// <returns>矩阵中的局部最小元素。</returns>
        static int MinimumRow(int[,] matrix, int rowStart, int rowLength, int colStart, int colLength)
        {
            int min = int.MaxValue;
            if (rowLength < 3)
                return int.MaxValue;
            int mid = rowStart + rowLength / 2;
            int minCol = 0;
            // 获取矩阵中间行的最小值
            for (int i = 0; i < colLength; ++i)
            {
                if (min > matrix[mid, colStart + i])
                {
                    min = matrix[mid, colStart + i];
                    minCol = i;
                }
            }
            // 检查是否满足条件
            if (matrix[mid, minCol] < matrix[mid - 1, minCol] && matrix[mid, minCol] < matrix[mid + 1, minCol])
            {
                return matrix[mid, minCol];
            }
            // 如果不满足则向较小一侧移动
            if (matrix[mid - 1, minCol] > matrix[mid + 1, minCol])
            {
                return MinimumCol(matrix, rowStart, rowLength, mid + 1, colLength / 2 + 1);
            }
            else
            {
                return MinimumCol(matrix, rowStart, rowLength, colStart, colLength / 2 + 1);
            }
        }

        /// <summary>
        /// 在矩阵中间列查找局部最小。
        /// </summary>
        /// <param name="matrix">矩阵。</param>
        /// <param name="rowStart">实际查找范围的行起始。</param>
        /// <param name="rowLength">实际查找范围的行结尾。</param>
        /// <param name="colStart">实际查找范围的列起始。</param>
        /// <param name="colLength">实际查找范围的列结尾。</param>
        /// <returns>矩阵中的局部最小元素。</returns>
        static int MinimumCol(int[,] matrix, int rowStart, int rowLength, int colStart, int colLength)
        {
            int min = int.MaxValue;
            int n = matrix.GetLength(0);
            int mid = n / 2;
            int minRow = 0;

            // 获取矩阵中间列最小值
            for (int i = 0; i < n; ++i)
            {
                if (min > matrix[i, mid])
                {
                    min = matrix[i, mid];
                    minRow = i;
                }
            }
            // 检查是否满足条件
            if (matrix[minRow, mid] < matrix[minRow, mid - 1] && matrix[minRow, mid] < matrix[minRow, mid + 1])
            {
                return matrix[minRow, mid];
            }
            // 如果不满足则向较小一侧移动
            if (matrix[minRow, mid - 1] > matrix[minRow, mid + 1])
            {
                return MinimumRow(matrix, mid + 1, rowLength / 2 + 1, colStart, colLength);
            }
            else
            {
                return MinimumRow(matrix, rowStart, rowLength / 2 + 1, colStart, colLength);
            }
        }
    }
}

另请参阅

POJ-滑雪

上一题 下一题