如何高效统计序列中值的变化次数？含实例解析

Great question! Let's start by confirming your example: for the sequence s = [1, -1, 1, 1, 1, -1], the number of value changes is indeed 3—each transition between different consecutive values counts as one change (1→-1, -1→1, 1→-1).

Optimal Approach & Time Complexity #

First, let's break down why the best possible time complexity here is O(n) (where n is the length of the sequence). To catch every value change, you have to check every pair of adjacent elements at least once—there's no way to skip any pair and still be sure you haven't missed a transition. This means linear time is the absolute minimum we can achieve, since we have to traverse the sequence exactly once.

This method is also space-efficient, using O(1) constant space: we only track a counter and the previous element, no extra data structures that grow with the sequence size.

Step-by-Step Implementation #

Here's how to implement this (the logic translates easily to most programming languages):

• Initialize a counter to 0.
• If the sequence has fewer than 2 elements, return 0 immediately—there are no pairs to compare, so no changes possible.
• Iterate from the second element to the end, comparing each element to the previous one.
• Every time consecutive elements differ, increment the counter and update the "previous" element to the current one.

Code Example (Python) #

def count_value_changes(sequence):
    if len(sequence) < 2:
        return 0
    change_count = 0
    prev_val = sequence[0]
    for current_val in sequence[1:]:
        if current_val != prev_val:
            change_count += 1
            prev_val = current_val
    return change_count

# Test with your sample sequence
s = [1, -1, 1, 1, 1, -1]
print(count_value_changes(s))  # Output: 3

Quick Walkthrough of Your Sample #

Let's verify the result manually to make sure it checks out:

1. Start with prev_val = 1, counter = 0
2. Next element is -1 (different from 1): counter becomes 1, prev_val updates to -1
3. Next element is 1 (different from -1): counter becomes 2, prev_val updates to 1
4. Next two elements are 1 (same as prev): no changes to the counter
5. Last element is -1 (different from 1): counter becomes 3

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