Question

1157. Online Majority Element In Subarray

中文文档

Description

Design a data structure that efficiently finds the majority element of a given subarray.

The majority element of a subarray is an element that occurs threshold times or more in the subarray.

Implementing the MajorityChecker class:

• MajorityChecker(int[] arr) Initializes the instance of the class with the given array arr.
• int query(int left, int right, int threshold) returns the element in the subarray arr[left...right] that occurs at least threshold times, or -1 if no such element exists.

 

Example 1:

Input
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
Output
[null, 1, -1, 2]

Explanation
MajorityChecker majorityChecker = new MajorityChecker([1, 1, 2, 2, 1, 1]);
majorityChecker.query(0, 5, 4); // return 1
majorityChecker.query(0, 3, 3); // return -1
majorityChecker.query(2, 3, 2); // return 2

 

Constraints:

• 1 <= arr.length <= 2 * 104
• 1 <= arr[i] <= 2 * 104
• 0 <= left <= right < arr.length
• threshold <= right - left + 1
• 2 * threshold > right - left + 1
• At most 104 calls will be made to query.

Solutions

Solution 1: Segment Tree + Boyer-Moore Voting Algorithm + Binary Search

We notice that the problem requires us to find the possible majority element in a specific interval, so we consider using a segment tree to maintain the candidate majority element and its occurrence in each interval.

We define each node of the segment tree as Node, each node contains the following attributes:

• l: The left endpoint of the node, the index starts from $1$.
• r: The right endpoint of the node, the index starts from $1$.
• x: The candidate majority element of the node.
• cnt: The occurrence of the candidate majority element of the node.

The segment tree mainly has the following operations:

• build(u, l, r): Build the segment tree.
• pushup(u): Use the information of the child nodes to update the information of the parent node.
• query(u, l, r): Query the interval sum.

In the initialization method of the main function, we first create a segment tree, and use a hash table $d$ to record all indexes of each element in the array.

In the query(left, right, threshold) method, we directly call the query method of the segment tree to get the candidate majority element $x$. Then use binary search to find the first index $l$ in the array that is greater than or equal to $left$, and the first index $r$ that is greater than $right$. If $r - l \ge threshold$, return $x$, otherwise return $-1$.

In terms of time complexity, the time complexity of the initialization method is $O(n)$, and the time complexity of the query method is $O(\log n)$. The space complexity is $O(n)$. Here, $n$ is the length of the array.

class Node:
  __slots__ = ("l", "r", "x", "cnt")

  def __init__(self):
    self.l = self.r = 0
    self.x = self.cnt = 0


class SegmentTree:
  def __init__(self, nums):
    self.nums = nums
    n = len(nums)
    self.tr = [Node() for _ in range(n << 2)]
    self.build(1, 1, n)

  def build(self, u, l, r):
    self.tr[u].l, self.tr[u].r = l, r
    if l == r:
      self.tr[u].x = self.nums[l - 1]
      self.tr[u].cnt = 1
      return
    mid = (l + r) >> 1
    self.build(u << 1, l, mid)
    self.build(u << 1 | 1, mid + 1, r)
    self.pushup(u)

  def query(self, u, l, r):
    if self.tr[u].l >= l and self.tr[u].r <= r:
      return self.tr[u].x, self.tr[u].cnt
    mid = (self.tr[u].l + self.tr[u].r) >> 1
    if r <= mid:
      return self.query(u << 1, l, r)
    if l > mid:
      return self.query(u << 1 | 1, l, r)
    x1, cnt1 = self.query(u << 1, l, r)
    x2, cnt2 = self.query(u << 1 | 1, l, r)
    if x1 == x2:
      return x1, cnt1 + cnt2
    if cnt1 >= cnt2:
      return x1, cnt1 - cnt2
    else:
      return x2, cnt2 - cnt1

  def pushup(self, u):
    if self.tr[u << 1].x == self.tr[u << 1 | 1].x:
      self.tr[u].x = self.tr[u << 1].x
      self.tr[u].cnt = self.tr[u << 1].cnt + self.tr[u << 1 | 1].cnt
    elif self.tr[u << 1].cnt >= self.tr[u << 1 | 1].cnt:
      self.tr[u].x = self.tr[u << 1].x
      self.tr[u].cnt = self.tr[u << 1].cnt - self.tr[u << 1 | 1].cnt
    else:
      self.tr[u].x = self.tr[u << 1 | 1].x
      self.tr[u].cnt = self.tr[u << 1 | 1].cnt - self.tr[u << 1].cnt


class MajorityChecker:
  def __init__(self, arr: List[int]):
    self.tree = SegmentTree(arr)
    self.d = defaultdict(list)
    for i, x in enumerate(arr):
      self.d[x].append(i)

  def query(self, left: int, right: int, threshold: int) -> int:
    x, _ = self.tree.query(1, left + 1, right + 1)
    l = bisect_left(self.d[x], left)
    r = bisect_left(self.d[x], right + 1)
    return x if r - l >= threshold else -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

class Node {
  int l, r;
  int x, cnt;
}

class SegmentTree {
  private Node[] tr;
  private int[] nums;

  public SegmentTree(int[] nums) {
    int n = nums.length;
    this.nums = nums;
    tr = new Node[n << 2];
    for (int i = 0; i < tr.length; ++i) {
      tr[i] = new Node();
    }
    build(1, 1, n);
  }

  private void build(int u, int l, int r) {
    tr[u].l = l;
    tr[u].r = r;
    if (l == r) {
      tr[u].x = nums[l - 1];
      tr[u].cnt = 1;
      return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }

  public int[] query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
      return new int[] {tr[u].x, tr[u].cnt};
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (r <= mid) {
      return query(u << 1, l, r);
    }
    if (l > mid) {
      return query(u << 1 | 1, l, r);
    }
    var left = query(u << 1, l, r);
    var right = query(u << 1 | 1, l, r);
    if (left[0] == right[0]) {
      left[1] += right[1];
    } else if (left[1] >= right[1]) {
      left[1] -= right[1];
    } else {
      right[1] -= left[1];
      left = right;
    }
    return left;
  }

  private void pushup(int u) {
    if (tr[u << 1].x == tr[u << 1 | 1].x) {
      tr[u].x = tr[u << 1].x;
      tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
    } else if (tr[u << 1].cnt >= tr[u << 1 | 1].cnt) {
      tr[u].x = tr[u << 1].x;
      tr[u].cnt = tr[u << 1].cnt - tr[u << 1 | 1].cnt;
    } else {
      tr[u].x = tr[u << 1 | 1].x;
      tr[u].cnt = tr[u << 1 | 1].cnt - tr[u << 1].cnt;
    }
  }
}

class MajorityChecker {
  private SegmentTree tree;
  private Map<Integer, List<Integer>> d = new HashMap<>();

  public MajorityChecker(int[] arr) {
    tree = new SegmentTree(arr);
    for (int i = 0; i < arr.length; ++i) {
      d.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
    }
  }

  public int query(int left, int right, int threshold) {
    int x = tree.query(1, left + 1, right + 1)[0];
    int l = search(d.get(x), left);
    int r = search(d.get(x), right + 1);
    return r - l >= threshold ? x : -1;
  }

  private int search(List<Integer> arr, int x) {
    int left = 0, right = arr.size();
    while (left < right) {
      int mid = (left + right) >> 1;
      if (arr.get(mid) >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * MajorityChecker obj = new MajorityChecker(arr);
 * int param_1 = obj.query(left,right,threshold);
 */

class Node {
public:
  int l = 0, r = 0;
  int x = 0, cnt = 0;
};

using pii = pair<int, int>;

class SegmentTree {
public:
  SegmentTree(vector<int>& nums) {
    this->nums = nums;
    int n = nums.size();
    tr.resize(n << 2);
    for (int i = 0; i < tr.size(); ++i) {
      tr[i] = new Node();
    }
    build(1, 1, n);
  }

  pii query(int u, int l, int r) {
    if (tr[u]->l >= l && tr[u]->r <= r) {
      return {tr[u]->x, tr[u]->cnt};
    }
    int mid = (tr[u]->l + tr[u]->r) >> 1;
    if (r <= mid) {
      return query(u << 1, l, r);
    }
    if (l > mid) {
      return query(u << 1 | 1, l, r);
    }
    auto left = query(u << 1, l, r);
    auto right = query(u << 1 | 1, l, r);
    if (left.first == right.first) {
      left.second += right.second;
    } else if (left.second >= right.second) {
      left.second -= right.second;
    } else {
      right.second -= left.second;
      left = right;
    }
    return left;
  }

private:
  vector<Node*> tr;
  vector<int> nums;

  void build(int u, int l, int r) {
    tr[u]->l = l;
    tr[u]->r = r;
    if (l == r) {
      tr[u]->x = nums[l - 1];
      tr[u]->cnt = 1;
      return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }

  void pushup(int u) {
    if (tr[u << 1]->x == tr[u << 1 | 1]->x) {
      tr[u]->x = tr[u << 1]->x;
      tr[u]->cnt = tr[u << 1]->cnt + tr[u << 1 | 1]->cnt;
    } else if (tr[u << 1]->cnt >= tr[u << 1 | 1]->cnt) {
      tr[u]->x = tr[u << 1]->x;
      tr[u]->cnt = tr[u << 1]->cnt - tr[u << 1 | 1]->cnt;
    } else {
      tr[u]->x = tr[u << 1 | 1]->x;
      tr[u]->cnt = tr[u << 1 | 1]->cnt - tr[u << 1]->cnt;
    }
  }
};

class MajorityChecker {
public:
  MajorityChecker(vector<int>& arr) {
    tree = new SegmentTree(arr);
    for (int i = 0; i < arr.size(); ++i) {
      d[arr[i]].push_back(i);
    }
  }

  int query(int left, int right, int threshold) {
    int x = tree->query(1, left + 1, right + 1).first;
    auto l = lower_bound(d[x].begin(), d[x].end(), left);
    auto r = lower_bound(d[x].begin(), d[x].end(), right + 1);
    return r - l >= threshold ? x : -1;
  }

private:
  unordered_map<int, vector<int>> d;
  SegmentTree* tree;
};

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * MajorityChecker* obj = new MajorityChecker(arr);
 * int param_1 = obj->query(left,right,threshold);
 */

type node struct {
  l, r, x, cnt int
}

type segmentTree struct {
  nums []int
  tr   []*node
}

type pair struct{ x, cnt int }

func newSegmentTree(nums []int) *segmentTree {
  n := len(nums)
  tr := make([]*node, n<<2)
  for i := range tr {
    tr[i] = &node{}
  }
  t := &segmentTree{nums, tr}
  t.build(1, 1, n)
  return t
}

func (t *segmentTree) build(u, l, r int) {
  t.tr[u].l, t.tr[u].r = l, r
  if l == r {
    t.tr[u].x = t.nums[l-1]
    t.tr[u].cnt = 1
    return
  }
  mid := (l + r) >> 1
  t.build(u<<1, l, mid)
  t.build(u<<1|1, mid+1, r)
  t.pushup(u)
}

func (t *segmentTree) query(u, l, r int) pair {
  if t.tr[u].l >= l && t.tr[u].r <= r {
    return pair{t.tr[u].x, t.tr[u].cnt}
  }
  mid := (t.tr[u].l + t.tr[u].r) >> 1
  if r <= mid {
    return t.query(u<<1, l, r)
  }
  if l > mid {
    return t.query(u<<1|1, l, r)
  }
  left, right := t.query(u<<1, l, r), t.query(u<<1|1, l, r)
  if left.x == right.x {
    left.cnt += right.cnt
  } else if left.cnt >= right.cnt {
    left.cnt -= right.cnt
  } else {
    right.cnt -= left.cnt
    left = right
  }
  return left
}

func (t *segmentTree) pushup(u int) {
  if t.tr[u<<1].x == t.tr[u<<1|1].x {
    t.tr[u].x = t.tr[u<<1].x
    t.tr[u].cnt = t.tr[u<<1].cnt + t.tr[u<<1|1].cnt
  } else if t.tr[u<<1].cnt >= t.tr[u<<1|1].cnt {
    t.tr[u].x = t.tr[u<<1].x
    t.tr[u].cnt = t.tr[u<<1].cnt - t.tr[u<<1|1].cnt
  } else {
    t.tr[u].x = t.tr[u<<1|1].x
    t.tr[u].cnt = t.tr[u<<1|1].cnt - t.tr[u<<1].cnt
  }
}

type MajorityChecker struct {
  tree *segmentTree
  d  map[int][]int
}

func Constructor(arr []int) MajorityChecker {
  tree := newSegmentTree(arr)
  d := map[int][]int{}
  for i, x := range arr {
    d[x] = append(d[x], i)
  }
  return MajorityChecker{tree, d}
}

func (this *MajorityChecker) Query(left int, right int, threshold int) int {
  x := this.tree.query(1, left+1, right+1).x
  l := sort.SearchInts(this.d[x], left)
  r := sort.SearchInts(this.d[x], right+1)
  if r-l >= threshold {
    return x
  }
  return -1
}

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * obj := Constructor(arr);
 * param_1 := obj.Query(left,right,threshold);
 */