c++计算出[L,R]中有多少个唯一不同数
时间: 2024-10-07 13:00:57 浏览: 19
在C++中,如果你想要计算一个区间[L, R]内有多少个唯一的整数,你可以通过使用哈希集合(如`std::unordered_set`)来实现。以下是步骤:
1. 首先,创建一个`std::unordered_set<int>`用于存储已经遇到过的数字。
2. 然后,遍历给定的范围[L, R]内的每一个整数。
3. 对于每个整数i,检查它是否已经在哈希集中。如果不在,说明是唯一的,将它添加到集合并计数。
4. 当遍历结束后,集合的大小就是区间[L, R]内唯一数字的数量。
这里是一个简单的伪代码示例:
```cpp
#include <unordered_set>
int countUnique(int L, int R) {
std::unordered_set<int> uniqueNumbers;
for (int i = L; i <= R; ++i) {
if (!uniqueNumbers.count(i)) {
uniqueNumbers.insert(i);
++count;
}
}
return count;
}
```
在这个函数中,`count`变量会记录唯一数字的个数。
相关问题
给定一个长度为 n 的整数数组 a1,a2,…,an ,数组中的每个元素都是一个 1∼n 之间的整数。 我们规定,数组中出现次数最多的元素为数组的核心元素,例如数组 [1,1,1,2,3] 的核心元素为 1 。 此外,如果数组中出现次数最多的元素不唯一,则出现次数最多的元素中数值最小的那个元素为数组的核心元素,例如数组 [1,2,2,3,3] 的核心元素为 2 。 对于 1≤i≤n 的每个整数 i ,请你计算有多少个给定数组的非空连续子数组的核心元素为 i 。c++代码
以下是对应的 C++ 代码实现:
```c++
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
map<int, int> freq;
int max_freq = 0;
int core = -1;
for (int i = 0; i < n; i++) {
freq[nums[i]]++;
if (freq[nums[i]] > max_freq || (freq[nums[i]] == max_freq && nums[i] < core)) {
max_freq = freq[nums[i]];
core = nums[i];
}
}
vector<int> count(n + 1);
int l = 0, r = 0;
int ans = 0;
while (r < n) {
count[nums[r]]++;
while (count[core] * 2 <= r - l + 1 && l <= r) {
count[nums[l]]--;
l++;
}
ans += count[core];
r++;
}
for (int i = 1; i <= n; i++) {
cout << ans << " ";
if (nums[i - 1] == core) {
ans--;
}
}
return 0;
}
```
算法思路:
首先,我们需要遍历整个数组,记录出现次数最多的元素以及其出现次数。具体来说,我们可以使用哈希表(C++ 中的 `map`)来存储每个元素出现的次数,然后遍历哈希表,找到出现次数最多的元素。
接下来,我们需要统计以每个元素为核心的子数组个数。假设当前核心元素为 i,我们使用两个指针 l 和 r,初始时均指向数组的第一个位置。然后我们不断向右移动指针 r,并记录当前所遍历的子数组中各个元素出现的次数。当以 i 为核心的子数组长度小于等于 2*count[i] 时,我们需要向右移动指针 l,并更新各个元素出现的次数,直到以 i 为核心的子数组长度大于 2*count[i] 为止。
最后,我们记录以 i 为核心的子数组个数,然后继续移动指针 r,直到遍历完整个数组。
时间复杂度:
遍历整个数组需要 O(n) 的时间复杂度,统计以每个元素为核心的子数组个数也需要 O(n) 的时间复杂度。因此,总时间复杂度为 O(n)。
空间复杂度:
我们需要使用一个哈希表和一个数组来存储各个元素出现的次数,因此空间复杂度为 O(n)。
一个价格 p(p 为正整数)的不满度定义为: 首先将 p 看做一个由数字组成的字符串(不带前导 0); 然后,如果 p 的最后一个字符是 0,就去掉它。重复这一过程,直到 p 的最后一个字符不是 0; 记 p 的长度为 a,如果此时 p 的最后一位是 5,则不满度为 2a - 1;否则为 2a。 例如,150 的不满度为 3,而 180 则为 4,114514 的不满度为 12。 现在,多莉要卖出一些商品,她能接受的商品价格在 [L, R] 范围内,她希望商品不满度越小越好,请你给出一个不满度最低的价格。用C++实现,如果价格的最小不满度不唯一,则输出价格最低的那一个,1<=L<= R <=10^9
题目分析:
这道题目和上一个问题的区别在于,给定区间 $[L,R]$ 中的价格不再是连续的,因此我们不能直接使用二分法来查找最小不满度的价格。
但是,我们可以观察到一个性质:对于任意两个价格 $p$ 和 $q$,如果 $p$ 的不满度小于 $q$ 的不满度,那么 $p$ 的所有前缀都小于 $q$ 的相应前缀。例如,如果 $p=1000$,$q=1050$,则 $p$ 的不满度为 $4$,$q$ 的不满度为 $5$,因此 $p$ 的所有前缀 $1, 10, 100, 1000$ 都小于 $q$ 的相应前缀 $1, 10, 105$。
基于这个性质,我们可以使用贪心算法来解决这个问题。具体来说,我们从左到右依次处理价格的每一位,每次选择可以使不满度最小的数字。当存在多个数字可以使不满度最小时,我们选择最小的那个数字。这样,我们就可以得到价格的最小不满度,以及对应的价格。
代码实现:
下面是 C++ 的代码实现:
```cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 计算不满度
int calc(int price) {
string str = to_string(price);
int len = str.size();
// 去掉末尾的 0
while (len > 1 && str[len-1] == '0') {
len--;
str.pop_back();
}
// 判断最后一位是否为 5
if (str[len-1] == '5') {
return 2*len - 1;
} else {
return 2*len;
}
}
// 计算数字 x 的不满度
int calcDigit(int x, int limit) {
string str = to_string(x);
int len = str.size();
// 去掉末尾的 0
while (len > 1 && str[len-1] == '0') {
len--;
str.pop_back();
}
// 计算当前不满度
int res = 0;
if (str[len-1] == '5') {
res = 2*len - 1;
} else {
res = 2*len;
}
// 如果当前不满度已经超过限制,则返回 -1
if (res > limit) {
return -1;
}
// 计算剩余部分的最小不满度
for (int i = len-2; i >= 0; i--) {
// 如果当前不满度已经达到限制,则直接返回结果
if (res == limit) {
return stoi(str.substr(0, i+1));
}
// 如果当前位为 0,则跳过
if (str[i] == '0') {
continue;
}
// 计算替换当前位后的不满度
int newRes = res;
if (str[i] == '5') {
newRes = 2*(i+1) - 1;
} else {
newRes = 2*(i+1);
}
// 如果替换后的不满度小于当前不满度,则更新结果
if (newRes <= limit) {
str[i] = '5';
res = newRes;
}
}
return stoi(str);
}
// 计算区间 [L,R] 中的最小不满度价格
int search(int L, int R, int limit) {
int ans = -1;
int minRes = limit + 1;
for (int i = L; i <= R; i++) {
int res = calc(i);
if (res < minRes) {
ans = i;
minRes = res;
} else if (res == minRes) {
int newAns = calcDigit(i, limit);
if (newAns != -1 && newAns < ans) {
ans = newAns;
}
}
}
return ans;
}
int main() {
int L, R;
cin >> L >> R;
int limit = 2 * log10(R) + 1;
int ans = search(L, R, limit);
cout << ans << endl;
return 0;
}
```
代码解析:
我们定义了一个函数 calcDigit,用于计算数字 $x$ 的不满度,并找到可以使不满度最小的数字。它的实现很简单,我们首先计算 $x$ 的当前不满度,然后从后向前依次考虑每一位数字。如果当前位为 $0$,则跳过;否则,我们计算替换当前位后的不满度,并选择可以使不满度最小的数字。如果当前不满度已经达到限制,则直接返回结果。如果最终得到的不满度小于当前不满度,则更新结果。
接着,我们定义了一个函数 search,用于在区间 $[L,R]$ 中查找最小不满度的价格。它的实现很简单,我们从左到右依次处理每个价格,计算其不满度,并找到可以使不满度最小的价格。如果有多个价格的不满度相同,则选择最小的那个价格。在选择最小的价格时,我们可以调用 calcDigit 函数来找到可以使不满度最小的数字,并返回其对应的价格。最终,返回最小不满度的价格即可。
在 main 函数中,我们读入区间 $[L,R]$ 的值,然后确定不满度的范围 limit,调用 search 函数进行查找。最终的答案就是查找到的最小不满度的价格。
阅读全文