我正在处理一个面试问题...需要找到以下逻辑:
寻找一个索引`j`,使得元素`a[j]`大于`a[i]`(且`j我现在所做的是:
1)通过简单的`for循环`使用`O(n^2)`。
2)从左到右扫描元素时构建平衡二叉搜索树,并为第`i`个元素找到大于它的元素的索引。但是我意识到它可以轻松地为单个元素使用`O(n)`,因此对于整个数组使用`O(n^2)`。
我想知道是否有可能在`O(n)`或`O(n log n)`的时间内完成。如果是,请给一些提示。
编辑:我认为我无法解释我的问题。让我清楚地解释一下:
我想要在`arr[i]`左侧找到`arr[j]`,使得`(i-j)`尽可能大,并且`arr[j]>arr[i]`,并为所有索引`i`找到这个值,即`for(i=0 to n-1)`。
编辑2:示例 - `{2,3,1,6,0}`
- 对于2,答案为-1 - 对于3,答案为-1 - 对于1,答案为2(`i-j==2-0`) - 对于6,答案为-1 - 对于0,答案为4(`i-j==4-0`)
寻找一个索引`j`,使得元素`a[j]`大于`a[i]`(且`j我现在所做的是:
1)通过简单的`for循环`使用`O(n^2)`。
2)从左到右扫描元素时构建平衡二叉搜索树,并为第`i`个元素找到大于它的元素的索引。但是我意识到它可以轻松地为单个元素使用`O(n)`,因此对于整个数组使用`O(n^2)`。
我想知道是否有可能在`O(n)`或`O(n log n)`的时间内完成。如果是,请给一些提示。
编辑:我认为我无法解释我的问题。让我清楚地解释一下:
我想要在`arr[i]`左侧找到`arr[j]`,使得`(i-j)`尽可能大,并且`arr[j]>arr[i]`,并为所有索引`i`找到这个值,即`for(i=0 to n-1)`。
编辑2:示例 - `{2,3,1,6,0}`
- 对于2,答案为-1 - 对于3,答案为-1 - 对于1,答案为2(`i-j==2-0`) - 对于6,答案为-1 - 对于0,答案为4(`i-j==4-0`)
min
和max
,然后进行比较吗?即:[1. 查找min]; [2. 查找max]; [3. 对于给定的第i个元素,比较哪个更远 - min还是max]。
就是这样。根据线性顺序的定义,没有什么可以更远了。 - Alma Doi-j
应该是最大值,而不是arr[i]-arr[j]
。 - Aseem Goyal