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

私はいくつかの質問があるアルゴリズムを思いついた：

  • もっと良いものはありますか？:)
  • UPとSTRAIGHT_UPが両方とも「UP」であるというこの二元論を実現するために、メソッドで列挙型を使用しました。私には厄介なようです。助言がありますか？
  • より良いメソッド名はありますか？direction（）（+ return value）の種類は、STRAIGHTがdirではないことを意味します。しかし同時に、それはエムムの要素なのでです。うーん。
  • 指定されたアレイで機能します。そうでない状況がありますか？

-

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回スキャンし、最小値と最大値を登録します。

言及する価値
のあること：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 に答える