arrays - 查找小于其右侧某个元素的每个元素

Question

我需要找到一个向量中的元素，这些元素小于它后面的多个元素之一。在循环中很容易做到:

x = some_vector_values;
for m = 1 : length(x)
  if( any( x(m+1:end) > x(m) )
    do_such_and_such;
  end
end

但是速度快要我的命了。我正在挠头试图想出一个有效的解决方法，但我一无所获。数组长度可以是数千的数量级，我需要对许多不同的数组执行此操作。

Answer 1

这使用了 divide-and-conquer方法(类似于二分查找):

1. 找到向量的最大值。
2. 接受其左侧的所有元素，而拒绝最大值本身。
3. 对于最大值右侧的那些元素，应用步骤 1。

虽然我没有仔分割析过，但我认为平均复杂度是O(n)，或者最多O(< em>n log n)。内存为 O(n)。

结果是一个逻辑向量ind包含 true对于接受的元素和 false对于被拒绝的元素。最终结果将是 x(ind) .

x = [3 4 3 5 6 3 4 1];
n = numel(x);
ind = false(1,n); %// intiallization
s = 1; %// starting index of the part of x that remains to be analyzed
while s <= n %// if s > n we have finished
    [~, m] = max(x(s:end)); %// index of maximum within remaining part of x
    ind(s:s-2+m) = true; %// elements to its left are accepted
    s = s+m; %// update start of remaining part
end

通过更改 while 可以稍微减少运行时间条件 while s < n , 因为最后一个元素总是被拒绝。