优化时间和空间效率
以下的解法1都不是最优的解法,解法2才是面试官喜欢的解法 如果对空间没有要求,最好就是使用辅助空间去设计算法,以空间换时间,达到一个平衡 1.数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字 p163 解法1:数组排序后,排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。也就是说,这个数字就是统计学上的中位数。 解法2:数组中数字出现次数超过数组长度的一半,也就是说它出现的次数比其他所有数字出现的次数的和还要多,保存两个值,一个是数组中的数字value1,另一个是次数value2,初始化设置value1=数组第一个元素,value2=1;然后遍历链表,如果下一个数字和我们之前保存的数字value1相同,则次数value2加1,value1不变;否则,value1不变,value2减1。如果value2为0,那么在下一个数字的时候我们要重新保存value1的值,并且设置value2为1。最后我们要找的数字就是把value2设置成1的那个value1的值。 举个例子:有个数组是{1,2,3,1,1,1,4,5,1,1,2};初始化第一轮value1=1,value2=1;第二轮value1=1,value2=0;第三轮value1=3,value2=1,;第四轮value1=3,value2=0;第五轮value1=1,value2=1;第六轮value1=1,value2=2;第七轮value1=1,value2=1;第八轮value1=1,value2=0;第九轮value1=1,value2=1;第十轮value1=1,value2=2;第十一轮value1=1,value2=1;所以最后,1就是我们要找的数字。 2.输入一个长度是n的数组,寻找其中最小的k个数 p167 解法1:如果我们可以修改输入的数组,那么可以利用快速排序将数组先排序,排序之后位于最前面的k个数即所求。时间复杂度为O(nlogn) 解法2:如果不允许修改输入的数组,那么可以先假设数组前k个元素构建一个k个元素的最大堆,堆顶就是其中最大元素kn,那剩余的n-k个元素逐个和堆顶元素kn进行比较,如果小于kn,就替换堆顶元素,并重新构建最大堆。重复以上步骤,直到最后一个元素对比完成,那么k个元素的最大堆就是要寻找的最小的k个数。时间复杂度为O(nlogk) 3.输入两个链表,找出他们的第一个公共节点 p193 解法1:蛮力法,遍历第一个链表节点,每遍历到一个节点就和去遍历第二个链表的每个节点进行对比,如果重合,就找到了 时间复杂度是O(mn) 解法2:利用两个栈,遍历两个链表分别把节点放到两个栈里,然后从栈顶弹出节点进行比较,如果相同就继续弹出下一个节点,直到找到最后一个相同节点 时间复杂度是O(m+n) 空间复杂度也是O(m+n) 解法3(最优):由于两个链表的长度不一致,所以无法用两个指针同步走,所以可以先计算两个链表的长度,让较长的那个链表先走几步,然后在同步走,直到发现两个指针相等 时间复杂度是O(m+n) 总结: 降低时间复杂度的两种方法:第一种是采用更高效的算法。第二种是利用空间换时间。