阿里p7阿里健康2面20201218笔试算法（指针操作）

ゝ一纸荒年。 2022-12-28 14:30 116阅读 0赞

/*
       两个正序排序的数组，求合并后的第K个。两个数组内元素没有 0，找不到第 K 个数可以返回 0。
    
       示例 1：
       如果 K = 5
       >array1 = [1, 13, 16, 20]
       >array2 = [2, 8, 12, 27]
       >则第K个数是：13
    
       ====================================注意=========================================
       ====================================注意=========================================
       要求：
       1、不要申请额外的空间，比如：数组、List、Set、Map；变量定义的是可以；
       2、不要使用java的sort相关函数，当然也不要自己手写冒泡排序，本题不是考察排序算法；
       3、需要写单元测试，写在独立文件中，或写在本类main方法里;
       4、穷举想到的测试边界case，而不仅仅是题目中示例的case；
    */
    public class FindKSolution {
    
    	public int findK(int[] array1, int[] array2, int k) {
    		return 0;
    	}
    }

这道题考点比较多最主要的是对于代码风格和数据边界测试，以及边界定义的划分，主要考点在这里，实现代码：

public class FindKSolution {
    
        public Integer findK(int[] array1, int[] array2, int k) {
            //1.判断是否处于边界
            if(array1 == null || array2 == null){
                return null;
            }
            if(k<=0){
                return null;
            }
            if(k>array1.length+array2.length){
                return null;
            }
            //2.循环打点取数据判断是第k个值
            int i = 0;
            int j = 0;
            int point = 0;
            Integer value = null;
            while(true){
                //判断i 和 j 不能大于array1,array2 length
                if(i>=array1.length && j>=array2.length ){
                    break;
                }
                //获取相对的两个数组的值进行比较
                int a1 = -1;
                if(array1.length !=0&&i<array1.length) {
                    a1 = array1[i];
                }
                int a2 =-1;
                if(array2.length !=0&&j<array2.length){
                    a2 = array2[j];
                }
                //因为array1,array2是正序的数据,取最小值进行比较
                if((a1<a2 && a1!=-1)||a2<0){
                    value = a1;
                    i++;
                }else if((a1>=a2 && a2!=-1)||a1<0){
                    value = a2;
                    j++;
                }else {
                    break;
                }
                // 记录第几个数
                point ++;
                //当记录的第几个数等于k 时返回value
                if(point >= k){
                    return value;
                }
            }
            return null;
        }
    
        public static void main(String[] args) {
            FindKSolution findKSolution = new FindKSolution();
            int[] array1 = {1,13,16,20};
            int[] array2 = {2,8,12,27};
            int k= 5;
            Integer data1 = null;
            //预期合并数组  1,2,8,12,13,16,20,27
            data1 = findKSolution.findK(array1,array2,k);
            System.out.println("预期值 13 data:"+data1);
            //边界值8
            k=8;
            data1 = findKSolution.findK(array1,array2,k);
            System.out.println("预期值 27 data:"+data1);
            //边界值0
            k=0;
            data1 = findKSolution.findK(array1,array2,k);
            System.out.println("预期值 null data:"+data1);
            //边界值1
            k=1;
            data1 = findKSolution.findK(array1,array2,k);
            System.out.println("预期值 1 data:"+data1);
            //数组边界值 array1 少  array2 多
            array1 = new int[]{1, 13, 16, 20};
            array2 = new int[]{2};
            k=2;
            data1 = findKSolution.findK(array1,array2,k);
            System.out.println("预期值 2 data:"+data1);
            //1,2,13,16,20,
            k = 3;
            data1 = findKSolution.findK(array1,array2,k);
            System.out.println("预期值 13 data:"+data1);
            //数组边界值 array1 一边值小
            array1 = new int[]{1, 13, 16, 20};
            array2 = new int[]{21};
            k = 3;
            data1 = findKSolution.findK(array1,array2,k);
            System.out.println("预期值 16 data:"+data1);
        }
    }

输出结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NhaTczOTI5NTczMg_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NhaTczOTI5NTczMg_size_16_color_FFFFFF_t_70]: /images/20221120/834cf3b092994fbfb9df87eadae3c401.png