已排序的数组有重复元素
时间: 2024-04-08 12:34:44 浏览: 29
如果已排序数组中存在重复元素,我们可以修改插入的位置,以确保新的素插入到重复元素的最后一个位置面。
以下是修改后的代码:
```c#include <stdio.h>
void insert(int arr[], int n, int m) {
int = 0, right = n - 1;
int insert_pos = -1;
// 使用二分查找找到插入位置
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] <= m) {
right = mid - 1;
} else {
left = mid + 1;
insert_pos = mid;
}
}
// 在插入位置后的元素后移
for (int i = n - 1; i > insert_pos; i--) {
arr[i] = arr[i - 1];
}
// 插入新元素
arr[insert_pos + 1] = m;
}
int main() {
int n, m;
int arr[100];
// 输入已排序的数组
printf("请输入已排序数组的长度n(n <= 100):");
scanf("%d", &n);
printf("请输入已排序数组的元素(从大到小顺序):");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// 输入待插入的元素
printf("请输入待插入的整数m:");
scanf("%d", &m);
// 插入并保持有序
insert(arr, n, m);
n++;
// 输出新序列
printf("插入后的有序序列为:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
这段代码与之前的代码类似,但在二分查找中,我们将插入位置设为`insert_pos`,并将元素插入到`arr[insert_pos + 1]`的位置上。这样可以确保新的元素插入到重复元素的最后一个位置后面,保持数组有序性。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)