1000个数范围是[0,999],有2个相同的数,请设计算法找出来,用c++描述
时间: 2023-03-05 11:53:26 浏览: 241
算法的思路是,首先从0开始遍历数组,将每个元素与它的下一个元素进行比较,如果相同,则将其保存到结果数组中,然后继续遍历,直到数组末尾。代码如下:int arr[1000];
int result[1000];
int result_index = 0;for (int i = 0; i < 1000; i++) {
if (arr[i] == arr[i + 1]) {
result[result_index] = arr[i];
result_index++;
}
}
相关问题
用分治法求解众数问题 给定一个整数序列,每个元素出现的次数为重数,重数最大的元素称为众数。编写一个程序对递增有序序列a求众数。例如 S={1, 2, ,2, 2, 3, 3, 5},多重集S的众数是2,其重数为3。 请描述算法设计思路,并给出算法核心代码。
算法设计思路:
1. 如果序列中只有一个元素,则该元素为众数,直接返回。
2. 将序列分为两个子序列,分别对左右两个子序列递归调用求众数函数。
3. 如果左右两个子序列的众数相同,则该数为整个序列的众数,重数为左右子序列众数重数之和。
4. 如果左右两个子序列的众数不同,则需要判断哪个众数的重数更大,将重数更大的众数作为整个序列的众数。如果左右子序列的众数重数相等,则随意选择一个作为整个序列的众数。
算法核心代码:
```c++
int find_majority(int a[], int left, int right) {
if (left == right) { // 只有一个元素,直接返回该元素
return a[left];
}
int mid = (left + right) / 2; // 分为左右两个子序列
int left_majority = find_majority(a, left, mid); // 左子序列的众数
int right_majority = find_majority(a, mid+1, right); // 右子序列的众数
if (left_majority == right_majority) { // 左右子序列众数相同
return left_majority;
}
else { // 左右子序列众数不同
int left_count = count_occurrences(a, left, mid, left_majority); // 左子序列众数出现次数
int right_count = count_occurrences(a, mid+1, right, right_majority); // 右子序列众数出现次数
if (left_count > right_count) { // 左子序列众数重数更大
return left_majority;
}
else { // 右子序列众数重数更大,或者左右子序列众数重数相等
return right_majority;
}
}
}
int count_occurrences(int a[], int left, int right, int x) {
int count = 0;
for (int i = left; i <= right; i++) {
if (a[i] == x) {
count++;
}
}
return count;
}
```
其中 `find_majority` 函数是递归求解众数的函数,`count_occurrences` 函数用于计算某个数在给定区间内的出现次数。
离散化处理 题目描述: 在程序设计过程中,经常要用到离散化处理,将原始数据排序,使用排序后的编号(rank值)作为新的关键字进行操作。排序后所有键值相同的数离散化处理后对应同一个编号。 输入格式: 第1行:一个整数N。 第2行:有N个整数,每个数在10^9以内。 输出格式: 依次输出每个数的rank编号。 样例输入: 4 28 5 6 5 样例输出: 3 1 2 1 提示: 1<=N<=100,000。 注意:可能有相同整数。 算法1提示: 1) 先sort; 2) 去重; 3) 二分查找每个值的位置。 算法2提示: 每个结构体元素中记录3项内容:(1)值,(2)原来的下标,(3)按值排序后的整理下标。 1)先按结构体中的值排序; 2)整理排序后的序号; 3)再按原始下标排序,排序后直接输出。 时间限制: 1000ms 空间限制: 128MB
以下是C++的算法1代码实现:
```c++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int a[N];
vector<int> s;
int find(int x)
{
int l = 0, r = s.size()-1;
while(l < r)
{
int mid = l + r >> 1;
if(s[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a+1, a+n+1);
s.push_back(a[1]);
for(int i = 2; i <= n; i++)
if(a[i] != a[i-1]) s.push_back(a[i]);
for(int i = 1; i <= n; i++)
cout << find(a[i]) << " ";
return 0;
}
```
思路:先对原始数据进行排序,去重后得到一个不重复的数组s。然后对于每个数,用二分查找在s中找到它的位置,即为rank值。
时间复杂度:排序的复杂度为O(nlogn),去重的复杂度为O(n),二分查找的复杂度为O(logn),最终复杂度为O(nlogn)。
以下是C++的算法2代码实现:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
struct node
{
int val, id, rank;
}a[N];
bool cmp1(node x, node y)
{
return x.val < y.val;
}
bool cmp2(node x, node y)
{
return x.id < y.id;
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i].val;
a[i].id = i;
}
sort(a+1, a+n+1, cmp1);
int cnt = 1;
a[1].rank = cnt;
for(int i = 2; i <= n; i++)
{
if(a[i].val != a[i-1].val) cnt++;
a[i].rank = cnt;
}
sort(a+1, a+n+1, cmp2);
for(int i = 1; i <= n; i++)
cout << a[i].rank << " ";
return 0;
}
```
思路:用结构体存储每个数的值、原始下标和rank值。先按值进行排序,然后整理出rank值。最后按原始下标排序,输出rank值。
时间复杂度:排序的复杂度为O(nlogn),最终复杂度为O(nlogn)。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)