用C语言写这道题:题目描述 给定一个长度为 n 的整数数组 a ,数组中所有数字的绝对值都在 0 ~ n - 1 的范围内。 数组中某些数字是重复的,但是不知道有几个数字重复了,也不知道每个数字重复了几次。 请找出数组中所有重复的数字。 输入 输入包含两行 第一行输入一个整数 n ( 1 ≤ n ≤ 1000000 ) 。 第二行输入由空格分隔的 n 个数, a1,a2,a3,...,an ( 0 ≤ |ai| ≤ n - 1 ) 。 输出 按从小到大的顺序输出数组中所有的重复数字,如果数组中有某些数字不在 0 ~ n - 1 的范围内,或者没有重复的数字,则输出 -1 。 样例输入 8 2 3 5 4 3 2 6 7 样例输出 2 3
时间: 2023-02-20 08:51:21 浏览: 126
以下是一个可行的 C 语言代码实现:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000000
int a[MAX_N];
int main() {
int n, i;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
if (a[i] < 0 || a[i] >= n) {
printf("-1\n");
return 0;
}
}
for (i = 0; i < n; i++) {
while (a[i] != i) {
if (a[i] == a[a[i]]) {
printf("%d ", a[i]);
break;
}
int t = a[i];
a[i] = a[t];
a[t] = t;
}
}
printf("\n");
return 0;
}
```
相关问题
给定一个整数数组,请求出该数组中两数之差(绝对值)的最小值,并确定对应元素的位置。用C语言写
以下是用C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main() {
int n, i, j, min_diff = INT_MAX, diff, x, y;
printf("请输入数组长度:");
scanf("%d", &n);
int *arr = (int *)malloc(n * sizeof(int));
printf("请输入数组元素:");
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
diff = abs(arr[i] - arr[j]);
if (min_diff > diff) {
min_diff = diff;
x = i;
y = j;
}
}
}
printf("两数之差(绝对值)的最小值为:%d,对应的元素位置为:%d和%d\n", min_diff, x, y);
free(arr);
return 0;
}
```
运行结果示例:
```
请输入数组长度:5
请输入数组元素:3 8 1 5 9
两数之差(绝对值)的最小值为:1,对应的元素位置为:0和2
```
题目:给定一个长度为n的数组a,求出其中所有子数组的最大值和最小值之差的和。
题目分析:
对于一个长度为n的数组a,我们可以先通过枚举的方式遍历所有子数组。然后对于每个子数组,我们可以求出该子数组的最大值和最小值,最后将它们的差累加起来即可。
时间复杂度:O(n^3),空间复杂度:O(1)。
但是,这种暴力枚举的方法时间复杂度太高,不适合处理大规模的数据。因此,我们需要寻找更高效的算法。
我们可以使用动态规划来解决这个问题。具体地,我们可以维护两个状态数组:一个用来存储当前位置之前的最大值,另一个用来存储当前位置之前的最小值。然后我们可以通过这两个数组来计算每个子数组的最大值和最小值之差,并将它们的和累加起来。
时间复杂度:O(n),空间复杂度:O(n)。
C语言代码实现:
```c
#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int min(int a, int b) {
return a < b ? a : b;
}
int maxMinDiffSum(int a[], int n) {
int max_dp[n], min_dp[n], ans = 0;
max_dp[0] = min_dp[0] = a[0];
for (int i = 1; i < n; i++) {
max_dp[i] = max(max_dp[i-1] + a[i], a[i]);
min_dp[i] = min(min_dp[i-1] + a[i], a[i]);
ans += max_dp[i] - min_dp[i];
}
return ans;
}
int main() {
int a[] = {1, 2, 3, 4};
int n = sizeof(a) / sizeof(int);
int ans = maxMinDiffSum(a, n);
printf("%d\n", ans); // 输出10
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.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)
![](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)