Question

2936. 包含相等值数字块的数量

English Version

题目描述

给定一个整数数组 nums，其 下标从 0 开始。对于 nums，有以下性质：

• 所有相同值的元素都是相邻的。换句话说，如果存在两个下标 i < j，使得 nums[i] == nums[j]，那么对于所有下标 k，满足 i < k < j，都有 nums[k] == nums[i]。

由于 nums 是一个非常大的数组，这里提供了一个 BigArray 类的实例，该实例具有以下函数：

• int at(long long index): 返回 nums[i] 的值。
• long long size(): 返回 nums.length。

让我们把数组分成 最大 的块，使得每个块包含 相等的值。返回这些块的数量。

请注意，如果要使用自定义测试测试解决方案，对于 nums.length > 10 的测试行为是未定义的。

 

示例 1：

输入：nums = [3,3,3,3,3]
输出：1
解释：这里只有一个块，也就是整个数组（因为所有数字都相等），即：[3,3,3,3,3]。因此答案是 1。 

示例 2：

输入：nums = [1,1,1,3,9,9,9,2,10,10]
输出：5
解释：这里有 5 个块：
块号 1: [1,1,1,3,9,9,9,2,10,10]
块号 2: [1,1,1,3,9,9,9,2,10,10]
块号 3: [1,1,1,3,9,9,9,2,10,10]
块号 4: [1,1,1,3,9,9,9,2,10,10]
块号 5: [1,1,1,3,9,9,9,2,10,10]
因此答案是 5。

示例 3：

输入：nums = [1,2,3,4,5,6,7]
输出：7
解释：由于所有数字都是不同的，这里有 7 个块，每个元素代表一个块。因此答案是 7。 

 

提示：

• 1 <= nums.length <= 1015
• 1 <= nums[i] <= 109
• 在生成的输入中所有相同值的元素是相邻的。
• nums 的所有元素之和最多为 1015。

解法

方法一：二分查找

我们可以使用二分查找来找到每个块的右边界。具体地，我们从左到右遍历数组，对于每个下标 $i$，我们使用二分查找找到最小的下标 $j$，使得 $[i,j)$ 之间的所有元素都等于 $nums[i]$。然后我们将 $i$ 更新为 $j$，并继续遍历数组，直到 $i$ 大于等于数组的长度。

时间复杂度 $O(m \times \log n)$，其中 $m$ 是数组 $num$ 中不同元素的个数，而 $n$ 是数组 $num$ 的长度。空间复杂度 $O(1)$。

# Definition for BigArray.
# class BigArray:
#   def at(self, index: long) -> int:
#     pass
#   def size(self) -> long:
#     pass
class Solution(object):
  def countBlocks(self, nums: Optional["BigArray"]) -> int:
    i, n = 0, nums.size()
    ans = 0
    while i < n:
      ans += 1
      x = nums.at(i)
      if i + 1 < n and nums.at(i + 1) != x:
        i += 1
      else:
        i += bisect_left(range(i, n), True, key=lambda j: nums.at(j) != x)
    return ans

/**
 * Definition for BigArray.
 * class BigArray {
 *   public BigArray(int[] elements);
 *   public int at(long index);
 *   public long size();
 * }
 */
class Solution {
  public int countBlocks(BigArray nums) {
    int ans = 0;
    for (long i = 0, n = nums.size(); i < n; ++ans) {
      i = search(nums, i, n);
    }
    return ans;
  }

  private long search(BigArray nums, long l, long n) {
    long r = n;
    int x = nums.at(l);
    while (l < r) {
      long mid = (l + r) >> 1;
      if (nums.at(mid) != x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

/**
 * Definition for BigArray.
 * class BigArray {
 * public:
 *   BigArray(vector<int> elements);
 *   int at(long long index);
 *   long long size();
 * };
 */
class Solution {
public:
  int countBlocks(BigArray* nums) {
    int ans = 0;
    using ll = long long;
    ll n = nums->size();
    auto search = [&](ll l) {
      ll r = n;
      int x = nums->at(l);
      while (l < r) {
        ll mid = (l + r) >> 1;
        if (nums->at(mid) != x) {
          r = mid;
        } else {
          l = mid + 1;
        }
      }
      return l;
    };
    for (long long i = 0; i < n; ++ans) {
      i = search(i);
    }
    return ans;
  }
};

/**
 * Definition for BigArray.
 * class BigArray {
 *   constructor(elements: number[]);
 *   public at(index: number): number;
 *   public size(): number;
 * }
 */
function countBlocks(nums: BigArray | null): number {
  const n = nums.size();
  const search = (l: number): number => {
    let r = n;
    const x = nums.at(l);
    while (l < r) {
      const mid = l + Math.floor((r - l) / 2);
      if (nums.at(mid) !== x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };

  let ans = 0;
  for (let i = 0; i < n; ++ans) {
    i = search(i);
  }
  return ans;
}

方法二：分治

我们可以使用分治的方法来计算答案。具体地，我们将数组分成两个子数组，递归地计算每个子数组的答案，然后将答案合并起来。如果第一个子数组的最后一个元素和第二个子数组的第一个元素相等，那么我们需要将答案减一。

时间复杂度 $O(\log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组 $num$ 的长度。

/**
 * Definition for BigArray.
 * class BigArray {
 *   public BigArray(int[] elements);
 *   public int at(long index);
 *   public long size();
 * }
 */
class Solution {
  public int countBlocks(BigArray nums) {
    return f(nums, 0, nums.size() - 1);
  }

  private int f(BigArray nums, long l, long r) {
    if (nums.at(l) == nums.at(r)) {
      return 1;
    }
    long mid = (l + r) >> 1;
    int a = f(nums, l, mid);
    int b = f(nums, mid + 1, r);
    return a + b - (nums.at(mid) == nums.at(mid + 1) ? 1 : 0);
  }
}

/**
 * Definition for BigArray.
 * class BigArray {
 * public:
 *   BigArray(vector<int> elements);
 *   int at(long long index);
 *   long long size();
 * };
 */
class Solution {
public:
  int countBlocks(BigArray* nums) {
    using ll = long long;
    function<int(ll, ll)> f = [&](ll l, ll r) {
      if (nums->at(l) == nums->at(r)) {
        return 1;
      }
      ll mid = (l + r) >> 1;
      int a = f(l, mid);
      int b = f(mid + 1, r);
      return a + b - (nums->at(mid) == nums->at(mid + 1));
    };
    return f(0, nums->size() - 1);
  }
};

/**
 * Definition for BigArray.
 * class BigArray {
 *   constructor(elements: number[]);
 *   public at(index: number): number;
 *   public size(): number;
 * }
 */
function countBlocks(nums: BigArray | null): number {
  const f = (l: number, r: number): number => {
    if (nums.at(l) === nums.at(r)) {
      return 1;
    }
    const mid = l + Math.floor((r - l) / 2);
    const a = f(l, mid);
    const b = f(mid + 1, r);
    return a + b - (nums.at(mid) === nums.at(mid + 1) ? 1 : 0);
  };
  return f(0, nums.size() - 1);
}