题目统计一个数字在排序数组中出现的次数。例如输入排序数组 {1,2,3,3,3,3,4,5}和数字3，由于3在这个数组出现了4次，因此输出4。 分析对排序的数组使用二分查找，主要为了确定目标数字k的第一个位置和最后一个位置。在一次查找过程中，存在3种情况： 如果中间数字比k小，则在数组的后半段进行 ...

题目输入两个链表，找出它们的第一个公共节点。 分析方法一蛮力法：在第一个链表上顺序遍历每个节点，每遍历到一个节点的时候，在第二个链表上顺序遍历每个节点。如果在第二个链表上有一个节点和第一个链表上的节点一样，说明两个链表在这个节点上重合。 时间复杂度是$O(mn)$，m和n分别为两个链表的长度。 方法 ...

题目在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 分析方法一从头到尾扫描数组，没扫描到一个数字，就逐个比较该数字和后面的数字的大小，时间复杂度是 $O(n^2)$。 方法二先把数组分隔成子数组， 先统计出子数组内部的逆序对 ...

题目在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”，则输出“b”。 分析字符是长度为8的数据类型，一共有256种可能，可以用一个数组模拟哈希表记录统计的次数。 实现1234567891011121314151617181920public class FirstNotRepeat ...

题目我们把只包含因子2、3和5的数称作丑数。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，习惯上把1称为第一个丑数。 分析方法一逐个判断每个整数是不是丑数，直观但不够高效。123456789boolean isUgly(int num){ while(num%2 = ...

题目输入一个正整数数组，把数组里所有数字都拼接起来排成一个数，打印能拼接处的所有数字中最小的一个。例如输入数组{3,32,321}，则打印出能排成的最小数字321323。 分析方法一求出所有数字的全排列，然后拼接起来，最后求出最大值。n个数字总共有 $n!$个排列。 方法二找到一个排序规则，数组根据 ...

#题目输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中国包含1的数字有1,10,11和12，1一共出现了5次。 分析如果直接累加1到n中每个整数出现1的次数，采用做除法和求余运算以求出该数字中1出现的次数。如果输入数字n，n有$O(\log{n})$ ...

题目输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个正数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如：输入的数组为{1,-2,3,10,-4,7,2,-5}，和最大的子数组为{3,10,-4,7,2}，因此输出为该子数组的和18。 分析如果使用枚举所有子数 ...

题目输入n个整数，找出其中最小的k个数。例如输入 4、5、1、6、2、7、3、8，则最小的4个数字是1、2、3、4。 分析方法一 时间复杂度最优是$O(n\log{n})$。 最简单的方法就是对整个输入的数字进行排序，然后取出前k个数。 方法二 时间复杂度是$O(n)$。 和29题的方法二一样 ...

题目数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个数组 {1,2,3,2,2,2,2,5,4,2}，会输出数字2。 分析方法一 时间复杂度最优是$O(n\log{n})$。 将整个数组进行排序，取出n/2索引处的数字即可。 方法二 时间复杂度是$O(n)$。 借用快速 ...