二进制数组判定：数组A的所有1是否均早于数组B的第一个1

Alright, let's break down this problem clearly. We have two binary arrays (only 0s and 1s) where all 1s in each array are consecutive—no scattered 1s like [1,0,1]. Our goal is to verify if every 1 in array A appears before the very first 1 in array B.

Key Observations #

Since all 1s are consecutive, we don't need to check every single 1 in A. Instead, we just need two critical positions:

• The last index of 1 in A: If this position is before the first 1 in B, then all 1s in A are automatically before that point (since they're consecutive).
• The first index of 1 in B: This is the earliest point where 1s start in B.

Edge Cases to Cover #

We also need to handle scenarios where one or both arrays have no 1s:

• If A has no 1s: The condition is automatically true (there's nothing to violate it).
• If B has no 1s: If A has any 1s, the condition fails (there's no "first 1 in B" for A's 1s to come before).
• If both arrays have no 1s: The condition is true (no conflicting elements).

Step-by-Step Implementation (Python Example) #

Here's a straightforward function that implements this logic:

def check_a_ones_before_b_first(A, B):
    # Find the last index of 1 in A
    last_a_one = -1
    for idx, num in enumerate(A):
        if num == 1:
            last_a_one = idx
    
    # Find the first index of 1 in B
    first_b_one = len(B)  # Default to array length if no 1s exist
    for idx, num in enumerate(B):
        if num == 1:
            first_b_one = idx
            break  # Stop at the first 1 we find
    
    # Evaluate the condition
    if last_a_one == -1:
        return True  # A has no 1s, condition holds
    if first_b_one == len(B):
        return False  # B has no 1s but A does, condition fails
    return last_a_one < first_b_one

Test Cases to Validate #

Let's run through some examples to confirm this works:

• Case 1 (True): A = [0,1,1,0], B = [0,0,0,1]
  Last 1 in A is index 2, first 1 in B is index 3 → 2 < 3 → returns True.
• Case 2 (True): A = [1,0,0,0], B = [0,1,1,0]
  Last 1 in A is index 0, first 1 in B is index 1 → 0 < 1 → returns True.
• Case 3 (False): A = [0,0,0,1], B = [0,1,0,0]
  Last 1 in A is index 3, first 1 in B is index 1 → 3 > 1 → returns False.
• Case 4 (True): A = [0,0,0,0], B = [1,1,1,1]
  A has no 1s → returns True.
• Case 5 (False): A = [1,1,1,1], B = [0,0,0,0]
  B has no 1s but A does → returns False.

内容的提问来源于stack exchange，提问作者tgordon18