128. 최 장 연속 시퀀스
Q:
정렬 되 지 않 은 정수 배열 을 지정 하여 최 장 연속 배열 의 길 이 를 찾 습 니 다.
알고리즘 의 시간 복잡 도 를 O (n) 로 요구 합 니 다.
예시:
입력: [100, 4, 200, 1, 3, 2] 출력: 4 해석: 최 장 연속 서열 은 [1, 2, 3, 4] 입 니 다.그것 의 길 이 는 4 이다.
A:
한 가지 주의 하 세 요. 제목 이 말 하 는 서열 의 길 이 는 몇 개의 연속 + 1 의 숫자 가 있 습 니 다.그 다음 에 문 제 는 정렬 을 하지 못 하 게 하고 dict 나 set 로 합 니 다. 그러면 O (N) 의 복잡 도 입 니 다. 비교적 교묘 한 부분 입 니 다. 현재 요소 에서 1 을 뺀 값 으로 집합 을 탐색 합 니 다. 존재 하면 현재 요 소 는 그 중의 가장 긴 연속 서브 시퀀스 의 출발점 이 아니 기 때문에 건 너 뛰 었 습 니 다.
c++：
1 class Solution {
2 public:
3 int longestConsecutive(vector<int>& nums) {
4 unordered_set<int> st;
5 for(int &num:nums){
6 st.insert(num);
7 }
8 int res=0;
9 for(int t:st){
10 if(st.count(t-1)){
11 continue;
12 }
13 int cnt=0;
14 while(st.count(t)){
15 ++t;
16 ++cnt;
17 }
18 res=max(res,cnt);
19 }
20 return res;
21 }
22 };python：
1 class Solution:
2 def longestConsecutive(self, nums: List[int]) -> int:
3 nums=set(nums)
4 res=1 if nums else 0
5 for x in nums:
6 if x-1 not in nums:
7 cur,y=1,x
8 while y+1 in nums:
9 cur+=1
10 y+=1
11 res=max(res,cur)
12 return res
13
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
