You are given an integer array nums and an integer target.
Return the number of subarrays of nums in which target is the majority element.
The majority element of a subarray is the element that appears strictly more than half of the times in that subarray.
Example 1:
Input: nums = [1,2,2,3], target = 2
Output: 5
Explanation:
Valid subarrays with target = 2 as the majority element:
nums[1..1] = [2]nums[2..2] = [2]nums[1..2] = [2,2]nums[0..2] = [1,2,2]nums[1..3] = [2,2,3]So there are 5 such subarrays.
Example 2:
Input: nums = [1,1,1,1], target = 1
Output: 10
Explanation:
All 10 subarrays have 1 as the majority element.
Example 3:
Input: nums = [1,2,3], target = 4
Output: 0
Explanation:
target = 4 does not appear in nums at all. Therefore, there cannot be any subarray where 4 is the majority element. Hence the answer is 0.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1091 <= target <= 109class Solution {
public int countMajoritySubarrays(int[] nums, int target) {
int n = nums.length, ans = 0, cumsum = 0;
int[] prefixSum = new int[n + 1];
for (int i = 0; i < n; i++) {
if (nums[i] == target)
cumsum++;
prefixSum[i + 1] = cumsum;
}
for (int i = 0; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (prefixSum[j] - prefixSum[i] > (j - i) / 2f)
ans++;
return ans;
}
}class Solution {
int target;
int[] nums;
class SegmentTree {
int[] tree;
SegmentTree(int n) {
this.tree = new int[4 * n];
}
void build(int idx, int lt, int rt) {
if (lt == rt) {
tree[idx] = (nums[lt] == target) ? 1 : 0;
return;
}
int mid = (lt + rt) / 2;
build(2 * idx + 1, lt, mid);
build(2 * idx + 2, mid + 1, rt);
tree[idx] = tree[2 * idx + 1] + tree[2 * idx + 2];
}
int query(int idx, int lt, int rt, int qlt, int qrt) {
if (rt < qlt || lt > qrt) // out of bounds
return 0;
if (lt >= qlt && rt <= qrt)
return tree[idx];
int mid = (lt + rt) / 2;
return query(2 * idx + 1, lt, mid, qlt, qrt)
+ query(2 * idx + 2, mid + 1, rt, qlt, qrt);
}
}
public int countMajoritySubarrays(int[] nums, int target) {
this.nums = nums;
this.target = target;
int n = nums.length, ans = 0;
SegmentTree tree = new SegmentTree(n);
tree.build(0, 0, n - 1);
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) {
// System.out.println("[" + i + "," + j + "]->"
// + tree.query(0, 0, n - 1, i, j) + "->" + ((j - i + 1) / 2f));
ans += (tree.query(0, 0, n - 1, i, j) > (j - i + 1) / 2f) ? 1 : 0;
}
return ans;
}
}class Solution {
int target;
int[] nums;
class SegmentTree {
int[] tree;
SegmentTree(int n) {
this.tree = new int[4 * n];
}
void build(int idx, int lt, int rt) {
if (lt == rt) {
tree[idx] = (nums[lt] == target) ? 1 : 0;
return;
}
int mid = (lt + rt) / 2;
build(2 * idx + 1, lt, mid);
build(2 * idx + 2, mid + 1, rt);
tree[idx] = tree[2 * idx + 1] + tree[2 * idx + 2];
}
int query(int idx, int lt, int rt, int qlt, int qrt) {
if (rt < qlt || lt > qrt) // out of bounds
return 0;
if (lt >= qlt && rt <= qrt)
return tree[idx];
int mid = (lt + rt) / 2;
return query(2 * idx + 1, lt, mid, qlt, qrt)
+ query(2 * idx + 2, mid + 1, rt, qlt, qrt);
}
}
public int countMajoritySubarrays(int[] nums, int target) {
this.nums = nums;
this.target = target;
int n = nums.length, ans = 0;
SegmentTree tree = new SegmentTree(n);
tree.build(0, 0, n - 1);
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) {
// System.out.println("[" + i + "," + j + "]->"
// + tree.query(0, 0, n - 1, i, j) + "->" + ((j - i + 1) / 2f));
ans += (tree.query(0, 0, n - 1, i, j) > (j - i + 1) / 2f) ? 1 : 0;
}
return ans;
}
}class Solution {
public int countMajoritySubarrays(int[] nums, int target) {
int n = nums.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
int cnt = 0;
for (int j = i; j < n; ++j) {
cnt += (nums[j] == target ? 1 : -1);
if (cnt > 0) {
++ans;
}
}
}
return ans;
}
}class Solution {
int target;
int[] nums;
class SegmentTree {
int[] tree;
SegmentTree(int n) {
this.tree = new int[4 * n];
}
void build(int idx, int lt, int rt) {
if (lt == rt) {
tree[idx] = (nums[lt] == target) ? 1 : 0;
return;
}
int mid = (lt + rt) / 2;
build(2 * idx + 1, lt, mid);
build(2 * idx + 2, mid + 1, rt);
tree[idx] = tree[2 * idx + 1] + tree[2 * idx + 2];
}
int query(int idx, int lt, int rt, int qlt, int qrt) {
if (rt < qlt || lt > qrt) // out of bounds
return 0;
if (lt >= qlt && rt <= qrt)
return tree[idx];
int mid = (lt + rt) / 2;
return query(2 * idx + 1, lt, mid, qlt, qrt)
+ query(2 * idx + 2, mid + 1, rt, qlt, qrt);
}
}
public int countMajoritySubarrays(int[] nums, int target) {
this.nums = nums;
this.target = target;
int n = nums.length, ans = 0;
SegmentTree tree = new SegmentTree(n);
tree.build(0, 0, n - 1);
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) {
// System.out.println("[" + i + "," + j + "]->"
// + tree.query(0, 0, n - 1, i, j) + "->" + ((j - i + 1) / 2f));
ans += (tree.query(0, 0, n - 1, i, j) > (j - i + 1) / 2f) ? 1 : 0;
}
return ans;
}
}