时间和 Space 计算活鱼的复杂度？

Question

我正在研究一个 Codility 问题：

You are given two non-empty zero-indexed arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.

The fish are numbered from 0 to N − 1. If P and Q are two fish and P < Q, then fish P is initially upstream of fish Q. Initially, each fish has a unique position.

Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:

0 represents a fish flowing upstream, 1 represents a fish flowing downstream. If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them. After they meet:

If A[P] > A[Q] then P eats Q, and P will still be flowing downstream, If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream. We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.

**Complexity:**

expected worst-case time complexity is O(N); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

这是我的解决方案：（100% 正确结果）

public int solution(int[] a, int[] b) {
  int remFish = a.length; 
  int i = 0; 
  for (i = 0; i < b.length; i++) {
    if(b[i] != 0){
      /*remFish++; }else { */ break; 
    }
  } 
  Stack<Integer> myQ = new Stack<Integer>(); 
  for (int j = i; j < b.length; j++) { 
    if(b[j] == 1)
    {
      myQ.add(j); 
    } 
    while(b[j] == 0 && !myQ.isEmpty()) {
      if(a[j] > a[myQ.peek()]){ 
        myQ.pop(); remFish--; 
      }else{ 
        remFish--; 
      break; 
      }
    } 
  } 
  return remFish;
}

有人可以帮助我了解我的解决方案是否满足复杂性要求吗？

Answer 1

由于奇怪的数据结构和缺少变量名，很难理解这段代码，但我认为我有必要的理解...

Space 复杂度: 您拥有的唯一维度 space 是 myQ，它受鱼的总量限制。因此，这是 O(n).

时间复杂度：鉴于你奇怪的逻辑，这更难理解。 remFish 的配对递减和 while -- break 的滥用让我困惑了几分钟。然而，更简单的分析是...

while -- break 将该循环变成一个简单的 if 语句，因为您总是在第一次迭代时中断循环。因此，您唯一真正的迭代是 for 循环，以鱼的数量为界。因此，这也是 O(n).

在其他属性中，请注意每次迭代都会递减 numFish，它永远不会下降到 0。

为什么您在 a.length 上衡量一次迭代，而在 b.length 上衡量另一次迭代？那些必须相同，鱼的起始数量。

Answer 2

N 鱼得到一系列 O(1) 检查。那是 O(n).

向下游游动的 O(n) 鱼被添加到 myQ 中，这也是 O(1) 每个 O(n) 项。

内循环的每次迭代都会在 O(1) 时间内杀死一条鱼。至多 O(n) 条鱼死掉所以那也是 O(n).

全部加起来，总数是O(n)。

Answer 3

你的idea不错。我试着让它更容易理解。

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {

        int numFishes = A.length;

        // no fishes
        if(numFishes == 0)
            return 0;

        // Deque stores the fishes swimming downstreams (B[i]==1) 
        Deque<Integer> downstreams = new ArrayDeque<Integer>();

        for(int i = 0; i < A.length; i++){

            //Fish is going downstreams
            if(B[i] == 1){
                // push the fish into the Deque
                downstreams.push(A[i]); 
            }//Fish is going upstreams
            else{
                while( !downstreams.isEmpty() ){ 
                    // Downstream-fish is bigger 
                    if( downstreams.peek() > A[i] ){
                        //Upstream-fish gets eaten
                        numFishes--;
                        break;    
                    }// Downstream-fish is smaller
                    else if(downstreams.peek() < A[i]){
                        //Downstream-fish gets eaten
                        numFishes--;
                        downstreams.pop();
                    }
                }
            }  
        }    

        return numFishes;
    }
}

Answer 4

我用这个代码得到了 100/100。我见过其他更简洁的解决方案。但是这个可读性很好。

ArrayDeque<Integer> downstreams = new ArrayDeque<>();
    int alive = 0;
    for (int i = 0; i < A.length; i++) {
        int currFish = A[i] * (B[i] == 1 ? -1 : 1);
        if (currFish < 0) {
            downstreams.push(currFish);
            alive++;
        } else {
            Iterator it = downstreams.iterator();
            boolean eaten = false;
            while (it.hasNext()) {
                int down = (int) it.next();
                if (Math.abs(currFish) > Math.abs(down)) {
                    it.remove();
                    alive--;
                    eaten = false;
                } else {
                    eaten = true;
                    break;
                }
            }
            if (!eaten) {
                alive++;
            }
        }
    }
    return alive;

Answer 5

这里是python3尝试时间复杂度O(N)

def fish_eater(fish_size, direction):
    stack = []
    fish_alive = len(fish_size)
    if not len(fish_size):
        return 0
    for i in range(len(fish_size)):
        if direction[i] == 1:
            stack.append(fish_size[i])
        else:
            while len(stack):
                if stack[-1] > fish_size[i]:
                    fish_alive -= 1
                    break
                if stack[-1] < fish_size[i]:
                    fish_alive -= 1
                    stack.pop()
    return fish_alive

关于时间复杂度和大 O 表示法的有用资源 understanding-time-complexity-with-python

时间和 Space 计算活鱼的复杂度？

Time and Space complexity for calculating many fish are alive?

java

algorithm

performance

time-complexity

space-complexity

这里是python3尝试时间复杂度O(N)