java - 2D Peak finding algorithm JAVA，找到了一个例子，但不会编码

Question

我正在尝试重建这个算法:
http://courses.csail.mit.edu/6.006/fall10/lectures/lec02.pdf
(第14页“算法二”)
(用谷歌找到这个，不幸的是我不在麻省理工学院 :) 这不是家庭作业)

这是:

•Pick middle column (j=m/2)
•Find global maximum a=A[i,m/2]in that column
    (and quit if m=1)
•Compare a to b=A[i,m/2-1]and c=A[i,m/2+1]
•If b>a   then recurse on left columns
•Else, if c>a   then recurse on right columns
•Else a is a 2D peak!  

我的是这样的:

trimmed 是一个 vector ，它保存我的大小频率 (blockSizeSmall-minBlockSize)。

所以它是一个带有 trimmed.size() 的二维矩阵列和 (blockSizeSmall-minBlockSize) 行。

为了简单起见，我将峰保存在 2 个 int vector 中 vector<int> peaksrow 和 peakscolumn。

有什么问题吗？
我不明白什么

"Find global maximum a=A[i,m/2]in that column (and quit if m=1)"

应该导致。

    public void findPeaks() {
        for (int column = trimmed.size() / 2; column < trimmed.size();) {
            int globalmax = 0;
            for (int row = 0; row < (blockSizeSmall - minBlockSize); row++) {
                if (trimmed.elementAt(column).reducedFreqs[row] > globalmax) {
                    globalmax = row; 
                    //find globalmax in row
                }
            }
            if (globalmax == 0) {
                break; //<- ???
            } else {
                if (column - 1 >= 0 && column + 1 < trimmed.size()) {
                //stay in bounds
                    if (trimmed.elementAt(column - 1).reducedFreqs[globalmax] > globalmax) {
                        column--; 
                        //if element at left side is > globalmax, recurse on column--;

                    } else if (trimmed.elementAt(column + 1).reducedFreqs[globalmax] > globalmax) {
                        column++; 
                        //if element at right side is > globalmax, recurse on column++;

                    } else { 
                        //if globalmax is higher than right or left element i have a peak
                        peaksrown.add(globalmax);
                        peakscolumnn.add(column);
                        Log.e(TAG, "" + peaksrown.size());
                    }
                }else{
                //what to do when out of bounds ?? break ??
                //if i break here, how can i be sure the algorithm 
                //went to both sides(column=0 and column=max) ??
                //just tried with break here, still infinit loop
                }
            }
        }
    }

它只是无限循环。

Answer 1

你似乎不理解递归的概念所以我建议你查一下。这是 C# 中的一种算法供引用，没有超出本文中的一个示例进行测试，但它应该可以工作。我忽略了“如果 m=1 则退出”部分，因为我认为不需要。请注意函数 Peak() 如何从自身内部调用自身，但参数已更改。

    static void Peak(int[,] map, int left, int right)
    {
        // calculate middle column
        int column = (right + left) / 2;


        // get max row in column
        int arow = 0;
        for (int row = 0; row < map.GetLength(0); row++)
            if (map[row, column] > map[arow, column])
                arow = row;

        int a = map[arow, column];

        // get left value
        int b = 0;
        if (column - 1 >= left) b = map[arow, column - 1];
        // get right value
        int c = 0;
        if (column + 1 <= right) c = map[arow, column + 1];

        // if left is higher, recurse left
        if (b > a) Peak(map, left, column - 1);
        // else if right is higher, recurse right
        else if (c > a) Peak(map, column + 1, right);
        // else, peak
        else Console.WriteLine("Peak: " + arow + " " + column + " " + a);
    }

    static void Main(string[] args)
    {
        int[,] map = { {12, 8, 5},
                       {11, 3, 6 },
                       {10, 9, 2 },
                       { 8, 4, 1 } };
        Peak(map, 0, 2);
        Console.ReadLine();
    }