class Solution {
public:
int numTeams(vector<int>& rating) {
}
};
1395. 统计作战单位数
n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。
每 3 个士兵可以组成一个作战单位，分组规则如下：
i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中 0 <= i < j < k < n请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。
示例 1：
输入：rating = [2,5,3,4,1] 输出：3 解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。
示例 2：
输入：rating = [2,1,3] 输出：0 解释：根据题目条件，我们无法组建作战单位。
示例 3：
输入：rating = [1,2,3,4] 输出：4
提示：
n == rating.length3 <= n <= 10001 <= rating[i] <= 10^5rating 中的元素都是唯一的原站题解
python3 解法, 执行用时: 72 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-17 21:30:59
class Solution:
def numTeams(self, rating: List[int]) -> int:
'''线段树模板'''
def add(i, delta): # 坐标i处依次添加delta
i += len(tree)//2 # 转换到线段树下标
while i > 0:
tree[i] += delta
i //= 2
def query(i, j): # 区域和检索 range sum
i += len(tree) // 2 # 转换到线段树下标
j += len(tree) // 2
summ = 0
while i <= j:
if i % 2 == 1: # i为右子树
summ += tree[i]
i += 1
if j % 2 == 0: # i为左子树
summ += tree[j]
j -= 1
i //= 2
j //= 2
return summ
'''主程序'''
# 离散化：绝对数值转秩次rank
uniques = sorted(rating) # rating没有重复值
rank_map = {v:i for i,v in enumerate(uniques)} #【注意：rank从0开始】
# print(rank_map)
# 构建线段树
tree = [0] * (len(rank_map) * 2)
# 枚举中间点
ans = 0
n = len(rating)
add(rank_map[rating[0]], 1) # 先将第一个元素入列
for i in range(1, n-1): # 从第二个元素开始遍历，直至倒数第二个元素
rank = rank_map[rating[i]] # 当前元素的排名/秩次
small1 = query(0, rank-1) # 查询前序元素中排名<rank的元素数目
large1 = i - small1 # small1 + large1 = i
small2 = rank - small1 # small1 + small2 = rank
large2 = n-1 - i - small2 # small2 + large2 = n-1-i
add(rank, 1) # 当前元素入列
ans += small1*large2 + large1*small2
return ans
python3 解法, 执行用时: 80 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-17 21:30:40
class Solution:
def numTeams(self, rating: List[int]) -> int:
def lowbit(x): # lowbit函数：二进制最低位1所表示的数字
return x & (-x)
def add(i, delta): # 单点更新：执行+delta
while i<len(tree):
tree[i] += delta
i += lowbit(i)
def query(i): # 前缀和查询
presum = 0
while i>0:
presum += tree[i]
i -= lowbit(i)
return presum
'''主程序'''
# 离散化：绝对数值转秩次rank
uniques = sorted(rating) # rating没有重复值
rank_map = {v:i+1 for i,v in enumerate(uniques)} #【rank从1开始】
# 构建树状数组
tree = [0] * (len(rank_map) + 1) # 树状数组下标从1开始
# 枚举中间点
ans = 0
n = len(rating)
add(rank_map[rating[0]], 1) # 先将第一个元素入列
for i in range(1, n-1): # 从第二个元素开始遍历，直至倒数第二个元素
rank = rank_map[rating[i]] # 当前元素的排名/秩次
small1 = query(rank-1) # 查询前序元素中排名<rank的元素数目
large1 = i - small1 # small1 + large1 = i
small2 = (rank-1) - small1 # 共有rank-1个元素排名<rank：small1 + small2 = rank-1
large2 = n-1 - i - small2 # small2 + large2 = n-1-i
add(rank, 1) # 当前元素入列
ans += small1*large2 + large1*small2
return ans
python3 解法, 执行用时: 84 ms, 内存消耗: 15.5 MB, 提交时间: 2022-11-17 21:30:09
class Solution:
def numTeams(self, rating: List[int]) -> int:
from sortedcontainers import SortedList
# 维护前后两个有序数组
sl1 = SortedList() # 存储i之前的元素
sl2 = SortedList(rating) # 存储i之后的元素
ans = 0
n = len(rating)
for i in range(n):
small1 = sl1.bisect_left(rating[i]) # 左侧小于当前值的元素数目
large1 = i - small1 # 左侧大于当前值的元素数目【满足small1+large1=i】
sl1.add(rating[i]) # sl1添加当前元素【为下一步准备】
sl2.remove(rating[i]) # sl2移除当前元素
small2 = sl2.bisect_left(rating[i]) # 右侧小于当前值的元素数目
large2 = n-1-i - small2 # 右侧大于当前值的元素数目【满足small2+large2=n-1-i】
ans += small1*large2 + large1*small2
return ans
java 解法, 执行用时: 12 ms, 内存消耗: 40.7 MB, 提交时间: 2022-11-17 21:29:12
class Solution {
int maxN;
int[] c;
List<Integer> disc;
int[] iLess;
int[] iMore;
int[] kLess;
int[] kMore;
public int numTeams(int[] rating) {
int n = rating.length;
maxN = n + 2;
c = new int[maxN];
disc = new ArrayList<Integer>();
for (int i = 0; i < n; ++i) {
disc.add(rating[i]);
}
disc.add(-1);
Collections.sort(disc);
iLess = new int[n];
iMore = new int[n];
kLess = new int[n];
kMore = new int[n];
for (int i = 0; i < n; ++i) {
int id = getId(rating[i]);
iLess[i] = get(id);
iMore[i] = get(n + 1) - get(id);
add(id, 1);
}
c = new int[maxN];
for (int i = n - 1; i >= 0; --i) {
int id = getId(rating[i]);
kLess[i] = get(id);
kMore[i] = get(n + 1) - get(id);
add(id, 1);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += iLess[i] * kMore[i] + iMore[i] * kLess[i];
}
return ans;
}
public int getId(int target) {
int low = 0, high = disc.size() - 1;
while (low < high) {
int mid = (high - low) / 2 + low;
if (disc.get(mid) < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public int get(int p) {
int r = 0;
while (p > 0) {
r += c[p];
p -= lowbit(p);
}
return r;
}
public void add(int p, int v) {
while (p < maxN) {
c[p] += v;
p += lowbit(p);
}
}
public int lowbit(int x) {
return x & (-x);
}
}
python3 解法, 执行用时: 988 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-17 21:28:24
class Solution:
def numTeams(self, rating: List[int]) -> int:
n = len(rating)
ans = 0
# 枚举三元组中的 j
for j in range(1, n - 1):
iless = imore = kless = kmore = 0
for i in range(j):
if rating[i] < rating[j]:
iless += 1
# 注意这里不能直接写成 else
# 因为可能有评分相同的情况
elif rating[i] > rating[j]:
imore += 1
for k in range(j + 1, n):
if rating[k] < rating[j]:
kless += 1
elif rating[k] > rating[j]:
kmore += 1
ans += iless * kmore + imore * kless
return ans
java 解法, 执行用时: 2385 ms, 内存消耗: 40.7 MB, 提交时间: 2022-11-17 21:27:06
class Solution {
public int numTeams(int[] rating) {
int n = rating.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
if ((rating[i] < rating[j] && rating[j] < rating[k]) || (rating[i] > rating[j] && rating[j] > rating[k])) {
++ans;
}
}
}
}
return ans;
}
}