求职面试的基本内容-使用链表、数组

请注意,对于长度为<2有一些琐碎的解决方案。此伪代码假定Arr[]的长度为>=2.

int Arr[] = {5,7,9,2,8,11,16,10,12};
int Sol[] = new int[9];

Stack<int> undecided;   // or a stack implemented using a linked list

Sol[0] = -1;    // this is a given

for(int i = Arr.length() - 1; i != 0; --i) {
    undecided.push(i); // we haven't found a smaller value for this Arr[i] item yet
                       // note that all the items already on the stack (if any)
                       // are smaller than the value of Arr[i] or they would have
                       // been popped off in a previous iteration of the loop
                       // below

    while (!undecided.empty() && (Arr[i-1] < Arr[undecided.peek()])) {
        // the value for the item on the undecided stack is
        //  larger than Arr[i-1], so that's the index for 
        //  the item on the undecided stack
        Sol[undecided.peek()] = i-1;
        undecided.pop();
    }
}

// We've filled in Sol[] for all the items have lesser values to
//  the left of them.  Whatever is still on the undecided stack
//  needs to be set to -1 in Sol

while (!undecided.empty()) {
    Sol[undecided.peek()] = -1;
    undecided.pop();
}

老实说,我不确定我会在10分钟的面试时间内想到这个问题。

在ideone上可以找到这方面的C++版本。通用域名格式: https://ideone.com/VXC0yq

    int Arr[] = {5,7,9,2,8,11,16,10,12};
    int Sol[] = new int[9];

    for(int i = 0; i < Arr.length; i++) {
        int element = Arr[i];

        int tmp = -1;
        for(int j = 0 ;j < i; j++) {
            int other = Arr[j];
            if (other < element) {
                tmp = j;                    
            }
        }

        Sol[i] = tmp;           
    }