-1

質問を投稿するのはこれが初めてです。何か間違っていたらご容赦ください。ここでの私の質問は、このコードからより高速なアルゴリズムを取得する方法ですか? 私は現在、ユーザーが入力を要求するインデックスの範囲から最小値を取得するようにコードを実装するために 2 つのスタックを使用しています。

例 (2,3,4,5,1)、(ユーザーが (1,4) を選択) の場合、(2,3,4,5) を見ていることを意味し、出力は 2 です。ありがとうございます。

import java.util.*;

interface StackADT <Integer> {
    // check whether stack is empty
    public boolean empty(); 

    // retrieve topmost item on stack
    public int       peek() throws EmptyStackException;

    // remove and return topmost item on stack
    public int       pop() throws EmptyStackException;

    // insert item onto stack
    public void    push(int item);
}


class StackArr <Integer> implements StackADT <Integer> {
    private int[] arr;
    private int top;
    private int maxSize;
    private final int INITSIZE = 1000;

    public StackArr() {
        arr = (int[]) new int[INITSIZE]; // creating array of type E
        top = -1;  // empty stack - thus, top is not on an valid array element
        maxSize = INITSIZE;
    }

    public boolean empty() { 
        return (top < 0); 
    }

    public int peek() throws EmptyStackException {
        if (!empty()) return arr[top];
        else throw new EmptyStackException();
    }

    public int pop() throws EmptyStackException {
        int obj = peek();
        top--;
        return obj;
    }

    public void push(int obj) {
        if (top >= maxSize - 1) enlargeArr();
        top++;
        arr[top] = obj;
    }
}


class RMQ{

    //declare stack object
    Stack<Integer> stack1;

    public RMQ(){
        stack1 = new Stack<Integer>();
    }

    public void insertInt(int num){
        stack1.push(num);
    }






    public int findIndex(int c, int d){



        Stack<Integer> tempStack = new Stack<Integer>();
        Stack<Integer> popStack = new Stack<Integer>();

        tempStack = (Stack)stack1.clone();

        while (d != tempStack.size())
        {
            tempStack.pop();            
        }

        int minValue = tempStack.pop();
        popStack.push(minValue);
        while (c <= tempStack.size())
        {
            int tempValue = tempStack.pop();
            if(tempValue >= minValue)
            {
                continue;
            }
            else
            {
                popStack.push(tempValue);
                minValue = tempValue;

            }
        }

        return popStack.pop();

    }


}




public class Pseudo{

    public static void main(String[] args){
        //declare variables
        int inputNum;
        int numOfOperations;

        //create object
        RMQ rmq = new RMQ();

        Scanner sc = new Scanner(System.in);

        //read input
        inputNum = sc.nextInt();


        //add integers into stack
        for(int i=0; i < inputNum; i++){
            rmq.insertInt(sc.nextInt());
        }

        // read input for number of queries
        numOfOperations = sc.nextInt();


        // Output queries
        for(int k=0; k < numOfOperations; k++){
           int output = rmq.findIndex(sc.nextInt(), sc.nextInt());
           System.out.println(output);
        }

    }
}
4

3 に答える 3

0

あなたの質問を理解する方法は、固定配列で前処理を行い、要素の範囲の検索最小操作を非常に高速にすることです。

この回答では、O(nlogn) 前処理作業を行い、続いて各クエリに対して O(1) 作業を行うアプローチについて説明しています。

前処理 O(nlogn)

アイデアは、2 次元配列 SMALL[a,k] を準備することです。ここで、SMALL[a,k] は、a で始まる 2^k 要素の最小値です。

この配列を再帰的に計算するには、k==0 から開始し、前の 2 つの要素を組み合わせて上位の各要素の値を作成します。

SMALL[a,k] = min(SMALL[a,k-1] , SMALL[a+2^(k-1),k-1])

クエリごとのルックアップ O(1)

次に、事前に準備された2つの回答を組み合わせることで、任意の範囲の最小値を即座に見つけることができます.

100 から 133 までの要素の最小値を見つけたいとします。100 から 131 までの 32 要素の最小値 (BIG[100,5]) と、102 から 133 までの 32 要素の最小値 (BIG[102 内) は既にわかっています。 ,5]) したがって、これらの最小のものを見つけて答えを得ることができます。

于 2013-10-18T12:23:39.180 に答える
0

なぜスタックを使用しているのですか？単純に配列を使用します。

int[] myArray = new int[inputNum];
// fill the array...

// get the minimum between "from" and "to"
int minimum = Integer.MAX_VALUE;
for(int i = from ; i <= to ; ++i) {
    minimum = Math.min(minimum, myArray[i])
}

以上です！

于 2013-10-18T11:39:09.923 に答える