Find consecutive elements in an array

http://www.1point3acres.com/bbs/thread-13711-1-1.html

Given an unsorted array of numbers. Find if the array consists of consecutive numbers after sorting. Do this in linear time.
Example 1: If array has 5,2,3,1,4,8, 10,11
Output:
1,2,3,4,5
8
10,11

我想到用计数排序，但是数组中数的范围不知道，所以不具有实际的可操作性

一旦没有什么好的思路，可以考虑下hash表

将<value, index>放入hash表中，用bool used[n]记录是否被访问过

遍历used中没有被访问过的数used[i] = true , a[i], 向左向右扩展a[i], 即a[i]+1, a[i]-1，是否在hash中，如果并且将对应的used记为flase。继续向左向右扩展，直至不能扩展为止

时间复杂度为o(n), 空间复杂度o(n)

总结

以上是生活随笔为你收集整理的Find consecutive elements in an array的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。