黑马程序员技术交流社区

标题: 发现毕老师视频中的一个不能解决的问题 [打印本页]
作者: 张明    时间: 2012-8-18 21:58
标题: 发现毕老师视频中的一个不能解决的问题
本帖最后由 张明 于 2012-8-19 05:14 编辑

先简要说明一下，基础视频第四天-7-数组(折半查找)
视频最后老师提出一个练习，在一个有序的数组中，插入一个数后，仍然保持数组有序性
老师的代码，只是通过折半查找实现了要插入的数插入在什么地方，这个大家都可以完成
问题所在，我要完整输出，怎么办？
  1. class charu
  2. {
  3. public static void main(String[] args)
  4. {
  5. int[] arr={0,1,2,3,5,6,7,8,0};//为简化，有效数字8以后手动给0
  6. int flag=0;
  7. for(int x=7;x>=0;x--)//为了说明问题，要有序插入4，手动赋值给x=7
  8. {
  9. if(arr[x]>4)//这个地方写>=也可以，>=就是把4插入到原数组4(若有)的前面
  10. arr[x+1]=arr[x];
  11. else
  12. {
  13. arr[x+1]=4;
  14. flag=1;
  15. }
  16. if(flag==1)//标记成功插入，避免0123被覆盖
  17. break;
  18. }
  19. for (int x=0;x<arr.length;x++ )
  20. {
  21. System.out.print(arr[x]);
  22. }
  23. }
  24. }
复制代码
（我服了啊，发了N次贴了，为什么我发代码就是没有格式呢，这个也求解）
运行结果，4已经成功插入正确地方

那么，在我代码的注释的地方，问题就来了
1.要插入一个数，数组必然要增大1，比插入数大的数为了保持有序性必须依次后移一位，老师没有写出来
2.我是手动给数组多加了一位0，在实际中就像视频中老师那样直接int[] arr={.....}，后移怎么解决？数组下标会越位报错的，这是最大的疑问，老师好像没有考虑到，下面详解
3.如果说有人直接定义int[] arr=new int[100]等，多定义一些元素不就可以了吗？那么请你想一想，我若有效元素只有0,1那么在数组中就是{0,1,0,0,0,0,.........}，还是要插入4，你怎么办？那不就是arr[99]=4了吗。arr.length这个值绝对等于100，这就是最大的缺陷，无法获取有效元素的真实长度
4.如果你还说从数组中第100个元素往前判断为0的元素忽略掉，那么，极端的情况就是有效元素是一个或多个0，{0,0,0,0,0......}，还是插入4，怎么办？说我太极端挑刺？那有负数和0在一起呢?{-2,1,0,0,0......}
只要有能在数组定义时定义比输入有效数据至少多一个元素，以上完美解决，但我真的不知道怎么定义

作者: 杜佳瑞    时间: 2012-8-18 22:15
楼主：
数组定义了就不能变长度了，你可以换个角度思考呀，比如重新定义一个数组，插入的同时把原来的元素都考过来，最后再数组赋值。
作者: 张明    时间: 2012-8-18 22:20
杜佳瑞 发表于 2012-8-18 22:15
楼主：
数组定义了就不能变长度了，你可以换个角度思考呀，比如重新定义一个数组，插入的同时把原来的元素 ...

{:3_64:}
为什么我没想到.........
这样的话，就只是内存多开辟一倍的空间，完美啊........
作者: 张明    时间: 2012-8-18 22:22
杜佳瑞 发表于 2012-8-18 22:15
楼主：
数组定义了就不能变长度了，你可以换个角度思考呀，比如重新定义一个数组，插入的同时把原来的元素 ...

哎，看老师的代码，在老师的基础上思考有点僵化了，不好不好
作者: hello world    时间: 2012-8-18 23:06
package cn.itcast.day23;

import java.util.Arrays;

public class ArrayInsert {

        public static void main(String[] args) {
                int[] arr = {1,2,3,5,6,7,8};
                int key =0;
                int location = getLocation(arr, key);
                int[] arr2 = new int[arr.length+1];
                if(location!=1){
                       
                        for(int i=0;i<arr2.length;i++){
                               
                                if(i<location){
                                        arr2[i]=arr[i];
                                }else if(i>location){
                                        arr2[i]=arr[i-1];
                                }else{
                                        arr2[location]=key;
                                }
                        }
                }else{
                        for(int i=1;i<arr2.length;i++){
                                arr2[0]=key;
                                arr2[i]=arr[i-1];
                        }
                }
               
                System.out.println(Arrays.toString(arr2));
        }
        public static int getLocation(int[] arr, int key){
                int i = 0;
                int j = arr.length-1;
                int mid=0;
                while(i<=j){
                        mid = (i+j)/2;
                        if(key>arr[mid]){
                                i=mid+1;
                        }else if(key<arr[mid]){
                                j=mid-1;
                        }else{
                                return mid;
                        }
                }
                return mid+1;
               
        }

}



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2