找到小于右边某个元素的每个元素

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

这使用了分而治之的方法(类似于二分搜索):

1. 找到向量的最大值.
2. 其左侧的所有元素都被接受,而最大值本身则被拒绝.
3. 对于最大权限的那些元素,应用步骤1.

虽然我没有仔细分析,但我认为平均复杂度为O(n),或者至多为O(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,因为最后一个元素总是被拒绝.

Answer 2

单线版

comparisons = any(triu(bsxfun(@gt,x(:).',x(:))),2)

Answer 3

你的算法很慢,因为if any(...)必须n在第一次迭代时检查项目,然后n-1在第二次迭代中检查项目......直到在最后一次迭代中检查单个项目.因此,它必须进行粗略的n^2/2比较,因此它的运行时间是输入向量长度的二次方!

一个时间和内存线性的解决方案可能是首先计算从该点到结束的最大值的向量,这可以在一个向后传递中计算(您可以将其称为反向累积最大值,不能进行矢量化).在此之后,此向量将直接与x(未经测试)进行比较:

% calculate vector mx for which mx(i) = max(x(i:end))
mx = zeros(size(x));
mx(end) = x(end);
for i = length(x)-1:-1:1 % iterate backwards
    mx(i) = max(x(i), mx(i+1));
end

for i = 1:length(x) - 1
    if mx(i) > x(i)
        do_such_and_such(i);
    end
end

如果您不关心do_such_and_such执行的顺序,这些for循环甚至可以像这样组合:

mx = x(end);
for i = length(x)-1:-1:1 % iterate backwards
    if x(i) < mx
        do_such_and_such(i);
    end
    mx = max(x(i), mx); % maximum of x(i:end)
end

Answer 4

这应该是一个需要O(n)时间和O(n)内存的算法:将数组中的最后一个元素标记为最大元素.向后遍历数组.每当元素小于最大值时,请保存.否则,它将成为您的新的最大值.这可以通过一次通过获得您需要的所有元素.