Tag Archives: Sorting

面试题—查找和排序

如果面试题要求在排序的数组(或者部分排序的数组)中查找一个数字或者统计某个数字出现的次数,都可以尝试用二分查找算法。如果需要在O(1)时间内查找某一元素,则考虑哈希表结构,其缺点是需要额外的空间来实现。

  1. 旋转数组的最小数字(二分查找)
    题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1. Continue reading