老师请帮忙看下,以下代码输出结果是否有问题,谢谢

老师请帮忙看下,以下代码输出结果是否有问题,谢谢

# 具体遇到的问题
按照样例代码输出7个数字的特殊数组
# 报错信息的截图
输出结果不符合作业中描述的结果,比如1和2的位置

after infixOrder arr[0, 6]1 5 3 0 2 4 6 

# 相关课程内容截图

生成数组:

// 生成一个长度为 n 的随机数组, 每个数字的范围是 [0, bound)
public static Integer[] generateSpecialArray(int n){

   Integer[] arr = new Integer[n];
   infixOrder(arr, 0, arr.length -1, 0, 0);
   return arr;
}

public static void infixOrder(Integer[] arr, int l, int r, int value, int depth){

   if(l > r) return;

   // 生成深度字符串
   String depthString = generateDepthString(depth);
   // 打印当前 sort 处理的数组区间信息
   System.out.print(depthString);
   System.out.println(String.format("infixOrder arr[%d, %d]", l, r));

   int mid = l + (r - l) / 2;
   arr[mid] = value;

   swap(arr, l, mid);
   infixOrder(arr, l + 1, r, value + 1,depth + 1);
   swap(arr, l, mid);

   // 打印当前 sort 处理的数组区间信息
   System.out.print(depthString);
   System.out.print(String.format("after infixOrder arr[%d, %d]", l, r));
   for(int i = l; i <= r; i++)
       System.out.print(arr[i] + " ");
   System.out.println();
}


执行:

int n = 7;

arr = ArrayGenerator.generateSpecialArray(n);


打印输出:

after infixOrder arr[0, 6]1 5 3 0 2 4 6 

# 尝试过的解决思路和结果
二叉树转数组也不对,请老师帮忙看下


# 粘贴全部相关代码,切记添加代码注释(请勿截图)

在这里输入代码,可通过选择【代码语言】突出显示

正在回答

登陆购买课程后可参与讨论,去登陆

1回答

抱歉,我没有特别理解你的问题。你的意思是,对于怎样的输入,你认为应该的输出结果是怎样的?你的算法实际的输出结果是怎样的?


==========


1 5 3 0 2 4 6 是正确的。


我们生成的测试用例,保证每次选择中间的元素做标定点,这个标定点是当前数组的最小值。


最初,选择 0 是标定点。经过第一轮 partition 以后,会变成 0 5 3 1 2 4 6,标定点 0 在最左边,之后处理 5 3 1 2 4 6,此时,中间的 1 依然是剩下未处理数组的最小值。


关键是,在快速排序的过程中, partition 会改变数组。我建议你使用这个生成的数组,实际运行快速排序(标定点选择中间值),运行试试看?再理解一下,我们为什么这么生成这个特殊的数组?


继续加油!:)


  • 慕粉1232246429 提问者 #1
    按照要求正确生成特殊数组输出,小的数字是否应该在每个数组的中间 after infixOrder arr[0, 6] 5 1 3 0 4 2 6 实际输出 after infixOrder arr[0, 6]1 5 3 0 2 4 6 这样的结果执行swap(arr, l, (l + r)/2);还是很快
    2020-11-11 09:57:34
  • liuyubobobo 回复 提问者 慕粉1232246429 #2
    我补充在原答案中了。生成的答案是正确的,你给出的答案是错误的:)
    2020-11-11 10:22:10
问题已解决,确定采纳
还有疑问,暂不采纳

恭喜解决一个难题,获得1积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2583    人
  • 解答问题       1082    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
意见反馈 帮助中心 APP下载
官方微信

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师