4

我正在尝试查找数组中所有局部最小值和最大值的索引。

例子：

int[] array = {5,4,3,3,3,3,3,2,2,2,  6,6,8,5,5,5,3,3,2,1,  1,4,4,7};
//                             |         |                 |
// Indices:    0,1,2,3,4,5,6,7,8,9, 10,1,2,3,4,5,6,7,8,9, 20,1,2,3
// Minima: 8, 20
// Maxima: 12

我想出了一个算法，对此我有几个问题：

  • 有更好的吗？:)
  • 我使用带有方法的 Enum 来实现 UP 和 STRAIGHT_UP 都是“UP”的二元论。对我来说似乎很乱。有什么建议么？
  • 你有更好的方法名称吗？direction() (+return value) 有点暗示 STRAIGHT 不是目录。但同时它也是，因为它是 Emum 中的一个元素。嗯。
  • 它适用于给定的数组。你看到没有的情况吗？

-

import java.util.ArrayList;


public class MinMaxFinder {
    private int[] array;
    private ArrayList<Integer> minima;
    private ArrayList<Integer> maxima;


    private enum Direction{
        UP, DOWN, STRAIGHT_UP, STRAIGHT_DOWN, STRAIGHT;

        public Direction direction(){
            if(this==UP || this==STRAIGHT_UP){
                return UP;
            }else if(this==DOWN || this==STRAIGHT_DOWN){
                return DOWN;
            }else{
                return STRAIGHT;
            }
        }

        public boolean isStraight(){
            if(this==STRAIGHT_DOWN || this==STRAIGHT_UP || this==STRAIGHT){
                return true;
            }else{
                return false;
            }
        }

        public boolean hasDifferentDirection(Direction other){
            if(this!=STRAIGHT && other!=STRAIGHT && this.direction() != other.direction() ){
                return true;
            }
            return false;
        }
    }

    public MinMaxFinder(int[] array){
        this.array = array;
    }

    public void update() {
        minima = new ArrayList<Integer>();
        maxima = new ArrayList<Integer>();

        Direction segmentDir = Direction.DOWN;
        int indexOfDirectionChange = 0;
        int prevVal = array[0];
        int arrayLength = array.length; 
        for(int i=1; i<arrayLength; i++){
            int currVal = array[i];
            Direction currentDir = currVal<prevVal?Direction.DOWN:(currVal>prevVal?Direction.UP:Direction.STRAIGHT);
            prevVal = currVal;

            if(currentDir.hasDifferentDirection(segmentDir)){
                int changePos = (indexOfDirectionChange+i-1)/2;
                if(currentDir.direction() == Direction.DOWN){
                    maxima.add(changePos);
                }else{
                    minima.add(changePos);
                }

                segmentDir = currentDir;
                indexOfDirectionChange = i;
            }else if( currentDir.isStraight() ^ segmentDir.isStraight() ){
                indexOfDirectionChange = i;

                if(currentDir.isStraight() && segmentDir.direction()==Direction.UP){
                    segmentDir=Direction.STRAIGHT_UP;
                }else if(currentDir.isStraight() && segmentDir.direction()==Direction.DOWN){
                    segmentDir=Direction.STRAIGHT_DOWN;
                }else{
                    segmentDir = currentDir;
                }
            }
        }
    }

    public ArrayList<Integer> getMinima() {
        return minima;
    }

    public ArrayList<Integer> getMaxima() {
        return maxima;
    }
}
4

3 回答 3

1

考虑一组一阶差分d[i] = a[i] - a[i-1]。

如果d[i]为正，则a在最后一步增加，如果d[i]为负，则a减少。因此，d从正到负的符号变化表明a局部最大值正在增加，现在正在减少。同样，从负到正表示局部最小值。

于 2012-10-31T12:59:49.183 回答
0

像这样的“应该”工作并且在概念上可能不那么复杂。扫描数组一次并记录最小值和最大值。

值得一提
的事情： 1) if(direction < 0){}else{} 大概可以去掉，但是我没有时间去想细节。
2) 关键思想是，根据第一个“方向”（我们首先看到的是最小值还是最大值），for 循环的顺序会发生变化。
3）如果有多个项目，它将始终保留最后一个元素（最高索引）。

if(a.length < 2){
       return;
   }

   List<Integer> mins = new ArrayList<Integer>();
   List<Integer> maxs = new ArrayList<Integer>();
   int i=1;
   int prev = 0;

   int direction = 0;
   for(int j=1, k = 0;j<a.length && (direction = a[j]-a[k]) == 0;j++, k++);

   if(direction == 0){
       //Array contains only same value.
       return;
   }

   if(direction < 0){
       while(i<a.length){
           for(;i<a.length && a[prev] >= a[i];i++,prev++);
           mins.add(prev);
           for(;i<a.length && a[prev] <= a[i];i++,prev++);
           maxs.add(prev);
           i++;prev++;
       }    
   }
   else{
       while(i<a.length){
           for(;i<a.length && a[prev] <= a[i];i++,prev++);
           maxs.add(prev);
           for(;i<a.length && a[prev] >= a[i];i++,prev++);
           mins.add(prev);
           i++;prev++;
       }
   }

   //maxs and mins now contain what requested
于 2012-10-31T13:48:49.520 回答
0

我想我明白了。多谢你们！你的想法对我帮助很大！

以下解决方案对我有用：

    ArrayList<Integer> mins = new ArrayList<Integer>();
    ArrayList<Integer> maxs = new ArrayList<Integer>();

    int prevDiff = array[0] - array[1];
    int i=1;
    while(i<array.length-1){    
        int currDiff = 0;
        int zeroCount = 0;
        while(currDiff == 0 && i<array.length-1){
            zeroCount++;
            i++;
            currDiff = array[i-1] - array[i];
        }

        int signCurrDiff = Integer.signum(currDiff);
        int signPrevDiff = Integer.signum(prevDiff);
        if( signPrevDiff != signCurrDiff && signCurrDiff != 0){ //signSubDiff==0, the case when prev while ended bcoz of last elem
            int index = i-1-(zeroCount)/2;
            if(signPrevDiff == 1){
                mins.add( index );
            }else{
                maxs.add( index );
            }               
        }
        prevDiff = currDiff;
    }
于 2012-10-31T16:08:33.043 回答