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

我想到用計數(shù)排序，但是數(shù)組中數(shù)的范圍不知道，所以不具有實際的可操作性

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

將<value, index>放入hash表中，用bool used[n]記錄是否被訪問過

遍歷used中沒有被訪問過的數(shù)used[i] = true , a[i], 向左向右擴展a[i], 即a[i]+1, a[i]-1，是否在hash中，如果并且將對應的used記為flase。繼續(xù)向左向右擴展，直至不能擴展為止

時間復雜度為o(n), 空間復雜度o(n)

總結

以上是生活随笔為你收集整理的Find consecutive elements in an array的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。