0°

面试算法知识梳理六:数组第三部分

内容预览:
  • 点击上方 &;程序员小乐&; ,选择“置顶公众号”,第一时间送达! 每日英文...~
  • 弯腰的时间久了,只会让人习惯于你的低姿态,你的不重要~
  •            while (curSum > sum &am...~

始发于微信公众号: 程序员小乐

专注于编程、互联网动态。最终将总结的技术、心得、经验(数据结构与算法、源码分析等)分享给大家,这里不只限于技术!还有职场心得、生活感悟、以及面经点击上方 “程序员小乐” ,选择“置顶公众号”,第一时间送达!

每日英文
There is a difference between knowing the path and walking the path.
“知道”和“做到”是两码事。

乐乐有话说
别总因为迁就别人就委屈自己,这个世界没几个人值得你总弯腰。弯腰的时间久了,只会让人习惯于你的低姿态,你的不重要 。

面试算法代码知识梳理系列

阅读目录

  • 1.概要

  • 2.实现

  • 2.1 在递增排序的数组中,查找指定数字出现的个数

  • 2.2 查找数组中只出现一次的两个数字

  • 2.3 在递增排序的数组中,查找和为 s 的两个数

  • 2.4 输入一个正数 s,打印出所有和为 s 的连续正数序列

  • 2.5 数组当中的最大最小值

一、概要

本文介绍了有关数组的算法第三部分的Java代码实现,所有代码均可通过 在线编译器(https://tool.lu/coderunner/) 直接运行,算法目录:

在递增排序的数组中,查找指定数字出现的个数
查找数组中只出现一次的两个数字
在递增排序的数组中,查找和为s的两个数
输入一个正数s,打印出所有和为s的连续正数序列
数组当中的最大最小值

二、代码实现

2.1 在递增排序的数组中,查找指定数字出现的个数

问题描述

在递增排序的数组中,查找指定数字出现的个数

解决思路

这个问题的关键信息是输入数组是 递增排序 的,指定数字必然是连在一起的,因此,我们只需要找到该数字第一次和最后一次出现的下标位置,那么就可以得到该数字出现的数字。

对于递增排序的数组,最常见的方法就是使用 二分查找,以查找数字第一次出现的位置为例,也就是下面的getFirstK函数:

如果只有一个元素,那么判断该元素是否是指定数字即可
如果只有两个元素,那么先判断前面的元素,如果不相等再判断后面的元素
如果大于两个元素,那么取中点位置的元素,如果该元素比需要查找的数字小,那么就说明需要查找的元素在其右侧,否则就说明它在查找元素的左侧(有可能包含该中点位置元素)。
getLastK也是同理。

代码实现

class Untitled {
   static int getFirstK(int p[], int num, int startIndex, int endIndex) {
       if (endIndex == startIndex) {
           return p[startIndex] == num ? startIndex : -1;
       }
       if (endIndex-startIndex == 1) {
           if (p[startIndex] == num) {
               return startIndex;
           } else if (p[endIndex] == num) {
               return endIndex;
           } else {
               return -1;
           }
       }
       int midOffset = (endIndex-startIndex) >> 1;
       //如果中间的元素比寻找的小,那么说明其在中间元素的右侧。
       if (p[startIndex+midOffset] < num) {
           return getFirstK(p, num, startIndex+midOffset+1, endIndex);
       } else {
           return getFirstK(p, num, startIndex, startIndex+midOffset);
       }
   }
   static int getLastK(int p[], int num, int startIndex, int endIndex) {
       if (endIndex == startIndex) {
           return p[startIndex] == num ? startIndex : -1;
       }
       if (endIndex-startIndex == 1) {
           if (p[endIndex] == num) {
               return endIndex;
           } else if (p[startIndex] == num) {
               return startIndex;
           } else {
               return -1;
           }
       }
       int midOffset = (endIndex-startIndex) >> 1;
       if (p[startIndex+midOffset] <= num) {
           return getLastK(p, num, startIndex+midOffset, endIndex);
       } else {
           //如果中间的元素比寻找的大,那么说明其在中间元素的左侧。
           return getLastK(p, num, startIndex, startIndex+midOffset-1);
       }
   }
   static int getNumberAppearTimes(int p[], int num, int len) {
       int firstK = getFirstK(p, 6, 0, len-1);
       int lastK = getLastK(p, 6, 0, len-1);
       if (firstK >= 0 && lastK >= 0) {
           System.out.println("firstK=" + firstK + ",lastK=" + lastK);
       }
       return lastK-firstK+1;
   }
   public static void main(String[] args) {
       int p[] = {1, 2, 3, 6, 6, 6, 9};
       int result = getNumberAppearTimes(p, 6, 7);
       System.out.println("appear=" + result);
   }
}

运行结果

firstK=3,lastK=5
appear=3

2.2 查找数组中只出现一次的两个数字

问题描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次,请写程序找出这两个只出现一次的数字。

解决思路

首先,让我们再复习一下异或的特点:两个相同的数异或的结果为0,且异或满足交换律和结合律。

对于题目中的假设,假如这两个只出现了一次的数为a和b:

第一步:对整型数组中的所有数进行异或,那么得到的结果就是a^b的值。
第二步:将a和b分到两个不同的子数组当中,再分别对这两个数组进行异或,那么就可以得到a和b了,而划分的依据就是根据第一步的结果,找出a^b中为1的一位。

代码实现

class Untitled {
   static void getTwoAppearOnce(int p[], int len) {
       int excluX = 0;
       int excluY = 0;
       for (int i=0; i<len; i++) {
          excluX ^= p[i];
       }
       System.out.println("全部异或结果=" + excluX);
       if (excluX != 0) {
           //确定两个出现唯一的元素,有一位一个为1,另一个为0。
           int diffBit = excluX^(excluX&(excluX-1));
           System.out.println("不相同的位=" + diffBit);
           excluX = 0;
           for (int i=0; i<len; i++) {
               //根据上面求出的位,分成两组,分别进行异或操作。
               if ((p[i] & diffBit) == 0) {
                   excluX ^= p[i];
               } else {
                   excluY ^= p[i];
               }
           }
           System.out.println("第一个元素=" + excluX + ",第二个元素=" + excluY);
       }
   }
   public static void main(String[] args) {
       int p[] = {1,3,3,5,7,7};
       getTwoAppearOnce(p, p.length);
   }
}

运行结果

全部异或结果=4
不相同的位=4
第一个元素=1,第二个元素=5

2.3 在递增排序的数组中,查找和为 s 的两个数

问题描述

在递增排序的数组中,查找和为s的两个数

解决思路

由于原数组是 递增排序 的,因此我们可以定义两个指针first和last,分别指向数组的首元素和尾元素,如果当前的和小于sum,那么说明需要放入一个更大的元素,就可以将首指针前移,如果小于sum,那么就将尾指针后移。

这里有一点需要注意,对于first和last已经移动过的位置,可以 确定其所在的元素 一定不是符合条件的两个数之一,因此,first不需要前移,last也不需要后移。

实现代码

class Untitled {
   static void findTwoNumberIsSumN(int p[], int len, int sum) {
       int first = 0;
       int last = len-1;
       while(first <= last) {
           int temp = p[first]+p[last];
           if (temp == sum) {
               System.out.println("p[first]=" + p[first] + ",p[last]=" + p[last]);
               break;
           } else if (temp < sum) {
               first++;
           } else {
               last--;
           }
       }  
   }
   public static void main(String[] args) {
       int p[] = {1,2,4,7,11,15};
       findTwoNumberIsSumN(p, p.length, 15);
   }
}

运行结果

p[first]=4,p[last]=11

2.4 输入一个正数 s,打印出所有和为 s 的连续正数序列

实现代码

class Untitled {
   static void getSerialNumberSumN(int sum) {
       int startNum = 1;
       int endNum = 2;
       int curSum = startNum+endNum;
       int max = (1+sum) >> 1;
       while (startNum < max) {
           if (curSum == sum) {
               System.out.println("[" + startNum + "..." + endNum + "]");
           }
           //如果当前的和大于要求的值,那么就移动首元素,使得数组的范围变小。
           while (curSum > sum && startNum < max) {
               //注意要先减再移位。
               curSum = curSum-startNum;
               startNum++;
               if (curSum == sum) {
                   System.out.println("[" + startNum + "..." + endNum + "]");
               }
           }
           //移动尾元素,使得数组的范围变大,注意要先移位之后再加。
           endNum++;
           curSum = curSum+endNum;
       }
   }
   public static void main(String[] args) {
       getSerialNumberSumN(15);
   }
}

运行结果

[1…5]
[4…6]
[7…8]

2.5 数组当中的最大最小值

实现代码

class Untitled {
   static class ValueHolder {
       public int maxNum;
       public int minNum;
   }
   static ValueHolder getMaxMinNumber(int p[], int startIndex, int endIndex) {
       ValueHolder value = new ValueHolder();
       if (startIndex == endIndex) {
           value.maxNum = p[startIndex];
           value.minNum = p[endIndex];
           return value;
       }
       int midOffset = (endIndex-startIndex) >> 1;
       ValueHolder l = getMaxMinNumber(p, startIndex, startIndex+midOffset);
       ValueHolder r = getMaxMinNumber(p, startIndex+midOffset+1, endIndex);
       if (l.maxNum >= r.maxNum) {
           value.maxNum = l.maxNum;
       } else {
           value.maxNum = r.maxNum;
       }
       if (l.minNum < r.minNum) {
           value.minNum = l.minNum;
       } else {
           value.minNum = r.minNum;
       }
       return value;
   }
   public static void main(String[] args) {
       int p[] = {1,45,23,3,6,2,7,234,56};
       ValueHolder v = getMaxMinNumber(p, 0, p.length-1);
       System.out.println("max=" + v.maxNum + ",min=" + v.minNum);
   }
}

运行结果

max=234,min=1

如果您觉得不错,请别忘了转发、分享、点赞让更多的人去学习, 您的举手之劳,就是对小乐最好的支持,非常感谢!

如何您想进技术群交流,关注公众号在后台回复 “加群”,或者 “学习” 即可

来自:泽毛

链接:https://www.jianshu.com/p/9af893281bb7

著作权归作者所有,欢迎投稿。

面试算法知识梳理六:数组第三部分


推荐阅读






看完本文有收获?请转发分享给更多人
关注「程序员小乐」,提升技能

以上就是:面试算法知识梳理六:数组第三部分 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论