AcWing 787. 归并排序模板_Java
原题链接
简单
作者:
zning
,
2019-09-19 08:15:34
,
所有人可见
,
阅读 4587
归并排序模板
犯过的错误
- 模板没有本下来, 递归的思路弄不清了
- 进行归并时, 使用 for循环 i++一次循环写了两次
- 归并操作时,
tmp[k++] = arr[i++]
错写成了 arr[k++] = arr[i++]
, 找了很半天的错误, 一定要仔细
代码
public class Main {
public static void main(String[] args) {
// 对输入值进行初始化
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
// 归并排序
merge_sort(arr, 0, n - 1);
// 打印输出
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// 归并排序
private static void merge_sort(int[] arr, int l, int r) {
// 递归结束条件
if (l >= r) return;
// 以下都为逻辑部分
int mid = l + ((r - l) >> 1);
merge_sort(arr, l, mid);
merge_sort(arr, mid + 1, r);
int[] tmp = new int[r - l + 1]; // 临时数组, 用于临时存储 [l,r]区间内排好序的数据
int i = l, j = mid + 1, k = 0; // 两个指针
// 进行归并
while (i <= mid && j <= r) {
if (arr[i] <= arr[j])
tmp[k++] = arr[i++];
else
tmp[k++] = arr[j++];
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= r) tmp[k++] = arr[j++];
// 进行赋值
for (i = l, j = 0; i <= r; i++, j++)
arr[i] = tmp[j];
}
}
用Scanner和print不会超时????
为啥我写的一样的代码会超时呀
我好像知道了,我的temp数组大小开的 r+1 ,改成 r-l+1 就好了。。。。
但是这个为啥会超时呀。
同问
啊,刚发了同问之后就想明白了,因为递归并不是只有外边的这一层,比如说,分到4份,也就是递归两次,这时候如果r+1时候,开的数组范围就恒定就是整个大数组的长度,而不是只需要的那对应的四分之一的长度
okok
你这里每次都new一个int数组不会很浪费时间吗…
在代码末尾结束这个就好了in.close();
数据加强后scanner会报错 java.util.NoSuchElementException
在代码末尾结束这个就好了in.close();
6666
mid 那里,我用l + r >> 1 才输出正确,用这个会死循环
并不会啊,这两种写法是一样的,你的这种可能会有越界问题
请问y总说的数组中只有两个数的情况, 我用java 出现了边界问题,大佬是怎么解决的
打印输出结果那里,如果用 System.out.printf(…) 就会TLE,xd遇到过吗?
需要用BufferedWriter
printf需要提供String类型的,你用print就没有
printf常用于格式转换,但需要注意不是换行输出,只用于精度转换(按照格式输出啊,保留小数啊)暂且看作是括号里必须要有双引号(String类),如果想输出整数类型的话(int i = 8;System.out.printf(“%d”,i);)
我也是这个问题