标题: [算法题] Amazon : Find consecutive elements in an array [打印本页] 作者: 孙宏雷 时间: 2013-7-30 13:10 标题: [算法题] Amazon : Find consecutive elements in an array Given an unsorted array of numbers. Find if the array consists ofconsecutive numbers after sorting. Do this in linear time.Example 1: If array has 5,2,3,1,4,8, 10,11Output:1,2,3,4,5810,11作者: 季良 时间: 2013-7-30 13:17
可以使用一个额外bool数组记录对应下标的元素是否已被归类.bool rec[n]也可以：1. 使用哈希表tbl记录元素值对应数组下标位置<value, index>2. 便利rec, 对每一个rec == false 的数a向两边扩展搜索连续值,比如如果在tbl里找到a-1对应下标为j, 则设rec[j] = true时间复杂度为O(n), 空间复杂度为O(n)