線性資料結構 --- array (3)

只有不斷學習,練習,,複習才會越來越厲害

因此開始記錄依照不同資料結構搭配Leetcode來練習

方便未來可以隨時拿來複習




Leetcode出處 : https://leetcode.com/problems/longest-consecutive-sequence/


                                 Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.



分析

因為題目說是unsorted integer，但是又說complexity必須是O(n)
因此，需要想到用hash table
我打算用unsorted_set來解此問題，並且以set裡面的元素為中心向外尋找下一個職是否在set裡，直到不連續為止
乍看之下時間複雜度是O(n^2)，但是因為在numsSet.erase(j)後，之前出現過的就不會再進入內層兩個迴圈裡，因此類積下來的次數就是nums元素個數。
另外，如果沒有說到要O(n)，我們可以先排序再做，因此時間複雜度就是O(n log n)



Sample Code (C++)

	class Solution {
	public:
	int longestConsecutive(vector<int>& nums) {
	int longestLen = 0;
	int currentLen = 0;
	unordered_set<int> numsSet;
	for (auto& i : nums)
	numsSet.insert(i);
	for (auto& i : nums) {
	currentLen = 1;
	/* Search smaller than i */
	for (int j = i-1; numsSet.find(j) != numsSet.end(); j--) {
	currentLen++;
	numsSet.erase(j);
	}
	/* Search bigger than i */
	for (int j = i+1; numsSet.find(j) != numsSet.end(); j++) {
	currentLen++;
	numsSet.erase(j);
	}
	longestLen = max(currentLen, longestLen);
	}
	return longestLen;
	}
	};

view raw .cpp hosted with ❤ by GitHub