锐客网

  1. 首页 > it技术 > >

Java面试题冲刺第二十天--手撸算法

目录

  • 手撸算法1：查找数组中重复元素和重复元素的个数
    • 1. 两层循环比较方式
    • 2. 转成Map集合处理方式
  • 手撸算法2：写个二分查找demo吧
    • 手撸算法3：把两个有序数组合并成一个有序数组
      • 总结

        手撸算法1：查找数组中重复元素和重复元素的个数 当听让我写这个算法时，纸笔还没给到我手上，作为一个资深MySQL爱好者，瞬间从裤裆掏出一杆笔，打个哈欠的功夫，就在面试官脸上写下了：
        select num,count(num) from T group by num order by count(num) desc;

        这个问题用的是数组，两层循环比较或Map都可以解决，比较简单，但是常问；方式如下：

        1. 两层循环比较方式
        package com.softsec.demo; import java.util.HashMap; import java.util.Map; import java.util.Random; /** * 查找数组中重复元素和重复元素的个数 * @author chenhh * */public class getRepeat { /*** 循环比较处理* @param arr*/ public static void cyclingDemo ( int[] arr){for (int x = 0; x < 10; x++) {int sumber1 = 0; for (int j = 0; j < 20; j++) {//数组中的数循环比较if (x == arr[j]) {sumber1++; } else {continue; }}System.out.println(x + " -- 重复个数:" + sumber1); } } public static void main (String[] args){Random random = new Random(); int[] arr = new int[20]; for (int i = 0; i < 20; i++) {arr[i] = random.nextInt(10); if (i < arr.length - 1) {System.out.print(arr[i]+"，"); } else {System.out.print(arr[i] + "\r\n 结果：" + "\r\n" ); }}// 输出arr数组中重复元素，重复数量// 循环处理cyclingDemo(arr); // map处理// mapDemo(arr); }

        打印结果：
        0，3，4，0，6，5，8，1，3，1，9，3，6，3，7，5，7，1，1，1
        结果：
        0 -- 重复个数:2
        1 -- 重复个数:5
        2 -- 重复个数:0
        3 -- 重复个数:4
        4 -- 重复个数:1
        5 -- 重复个数:2
        6 -- 重复个数:2
        7 -- 重复个数:2
        8 -- 重复个数:1
        9 -- 重复个数:1
        Process finished with exit code 0


        2. 转成Map集合处理方式
        package com.softsec.demo; import java.util.HashMap; import java.util.Map; import java.util.Random; /** * 查找数组中重复元素和重复元素的个数 * @author chenhh * */public class getRepeat { /*** 转成集合处理* @param arr*/ public static void mapDemo ( int[] arr){//将数据转成集合Map map = new HashMap(); for (int a = 0; a < arr.length; a++) {if (map.get(arr[a])!=null){map.put(arr[a],map.get(arr[a])+1); }else {map.put(arr[a],1); }}for (int i = 0; i <10 ; i++) {System.out.println(i + " -- 重复个数：" + map.get(i)); } }} public static void main (String[] args){Random random = new Random(); int[] arr = new int[20]; for (int i = 0; i < 20; i++) {arr[i] = random.nextInt(10); if (i < arr.length - 1) {System.out.print(arr[i]+"，"); } else {System.out.print(arr[i] + "\r\n 结果：" + "\r\n" ); }}// 输出arr数组中重复元素，重复数量// 循环处理// cyclingDemo(arr); // map处理mapDemo(arr); }}

        打印结果：
        2，2，7，7，1，6，1，7，1，9，1，2，1，9，9，4，0，3，5，1
        结果：
        0 -- 重复个数：1
        1 -- 重复个数：6
        2 -- 重复个数：3
        3 -- 重复个数：1
        4 -- 重复个数：1
        5 -- 重复个数：1
        6 -- 重复个数：1
        7 -- 重复个数：3
        8 -- 重复个数：null
        9 -- 重复个数：3
        Process finished with exit code 0


        手撸算法2：写个二分查找demo吧 二分查找的条件是对一组有序数组的查找，所以要先确定查找的数组是否有序，在使用二分查找的时候先要对数组进行排序。
        加个排序多麻烦？所以面试官不指定无序数组时，就都当有序的就行。无序你用什么二分法是吧？
        二分算法步骤
        1.首先确定整个查找区间的中间位置mid = （ left + right ）/ 2
        2.用待查关键字值与中间位置的关键字值进行比较；
        ★ 若相等，则查找成功

        ★ 若大于，则在后（右）半个区域继续进行折半查找

        ★ 若小于，则在前（左）半个区域继续进行折半查找
        3.对确定的缩小区域再按折半公式，重复上述步骤，使用递归或普通while循环都可以。
        这里我们对给定数列（有序）{ 1, 20, 23, 24, 35, 46, 77, 78, 99, 100}，通过二分法查找值为78的数据元素。
        package com.softsec.demo; /** * 二分查找算法，两种方法，一种递归一种非递归 * @author chenhh * */public class BinaryQry { public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = new int[] { 1, 20, 23, 24, 35, 46, 77, 78, 99, 100 }; int index = search(arr,0,arr.length-1,78); //int index = search2(arr, 11); if (index == -1) {System.out.println("没找到"); return; }System.out.println("在数组的第" + (index+1) + "位"); } /** 递归方法查找*/ public static int search(int[] arr, int left, int right, int key) {if (left <= right) {int mid = (left + right) / 2; if (key < arr[mid]) {return search(arr, left, mid - 1, key); } else if (key > arr[mid]) {return search(arr, mid + 1, right, key); } else {return mid; }}return -1; } /** 非递归方法查找*/ public static int search2(int[] arr, int key) {int left = 0; int right = arr.length - 1; int mid = 0; while (left <= right) {mid = (left + right) / 2; if (key == arr[mid]) {return mid; } else if (key > arr[mid]) {left = mid + 1; } else if (key < arr[mid]) {right = mid - 1; }}return -1; }}


        手撸算法3：把两个有序数组合并成一个有序数组 对于两个有序数组arrayM，arrayN，数组长度分别为m和n；
        思路：
        • 定义一个新数组newArray，长度为m+n；
        • 定义两个index（int），如：int start=0,end=0，用来记录数组arrayM、arrayN的下标；
        • 通过分别遍历数组arrayM和arrayN的方式来比较每个值的大小，并将值存放到newArray中；
        • 判断start和end是否分别小于m和n，如果小于则继续执行，否则则表示有一个array遍历结束，然后将另一个array剩余部分追加到newArray中即可；
        package com.softsec.demo; /** * 两个有序数组合并成一个有序数组的实现类 * @author chenhh * */public class ArrayMerge { /** * 数组合并方法 * @param arrayM * @param arrayN * @return */ public static int[] mergeArray(int arrayM[],int arrayN[]){int newArray[]; // 定义一个新数组，长度为两个有序数组长度之和newArray = new int[arrayM.length + arrayN.length]; // start:arrayM数组下标end：arrayN数组下标k：newArray新数组下标int start=0,end=0,k=0; // 循环比较两个数组，较小元素的放入新数组，较小元素所在数组下标加一，较大元素对应的数组下标不加一，直到某一个下标等于数组长度时退出循环while(start 结果打印：
        0，1，3，5，7，8，9，10，14，16，20，21，30，40，50
        Process finished with exit code 0

        总结 【Java面试题冲刺第二十天--手撸算法】本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注脚本之家的更多内容！

          推荐阅读


          上一篇：解析Java并发Exchanger的使用

          下一篇：Mybatis实现联表查询并且分页功能