배열에서 가장 긴 정사각형 줄무늬

2501. 배열에서 가장 긴 정사각형 줄무늬

난이도:중

주제: 배열, 해시 테이블, 이진 검색, 동적 프로그래밍, 정렬

정수 배열 nums가 제공됩니다. 다음과 같은 경우 숫자의 하위 수열을 사각형 줄무늬라고 합니다.

• 하위 시퀀스의 길이는 최소 2이고
• 하위 시퀀스를 정렬한 후 각 요소(첫 번째 요소 제외)는 이전 숫자의 사각형입니다.

가장 긴 정사각형 줄무늬의 길이를 숫자로 반환하거나, 사각형 줄무늬가 없으면 -1을 반환합니다.

하위 시퀀스는 나머지 요소의 순서를 변경하지 않고 일부 요소를 삭제하거나 요소를 전혀 삭제하지 않고 다른 배열에서 파생될 수 있는 배열입니다.

예 1:

• 입력: 숫자 = [4,3,6,16,8,2]
• 출력: 3
• 설명: 하위 수열 [4,16,2]를 선택하세요. 정렬하면 [2,4,16]이 됩니다.
  • 4 = 2 * 2.
  • 16 = 4 * 4.
  • 따라서 [4,16,2]는 정사각형 줄무늬입니다.
  • 길이가 4인 모든 하위 수열은 정사각형 줄무늬가 아님을 알 수 있습니다.

예 2:

• 입력: 숫자 = [2,3,5,6,7]
• 출력: -1
• 설명: 숫자에 정사각형 줄무늬가 없으므로 -1을 반환합니다.

제약조건:

• 2 5
• 2 <= 숫자[i] <= 10⁵

힌트:

1. 제약 조건에 따라 가능한 가장 긴 정사각형 줄무늬의 길이는 5입니다.
2. nums의 요소를 세트에 저장하면 해당 요소가 존재하는지 빠르게 확인할 수 있습니다.

해결책:

nums 배열에서 가장 긴 정사각형 줄무늬를 식별해야 합니다. 정사각형 줄무늬는 각 후속 요소가 이전 요소의 정사각형인 하위 수열이며 길이가 두 개 이상의 요소여야 합니다.

해결 방법은 다음과 같습니다.

1. 빠른 조회를 위해 세트 사용:

   • 요소의 사각형도 배열에 있는지 빠르게 확인하려면 숫자를 세트에 저장하세요.

2. 배열 반복:

   • 배열의 각 숫자에 대해 해당 숫자부터 시작하여 정사각형 줄무늬를 만들어 보세요.
   • 현재 숫자의 제곱이 세트에 있는지 확인하고 더 이상 일치하는 제곱이 없을 때까지 연속을 계속 연장하세요.

3. 트랙 최대 길이:

   • 발생할 수 있는 모든 정사각형 줄무늬의 최대 길이를 추적하세요. 정사각형 줄무늬가 발견되지 않으면 -1을 반환합니다.

4. 최적화:

   • 하위 시퀀스가 ​​오름차순으로 확인되도록 각 요소를 확인하기 전에 배열을 정렬하세요. 이렇게 하면 중복 확인을 방지하는 데 도움이 됩니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2501. 배열에서 가장 긴 정사각형 줄무늬

  
  
  설명:




정렬: 숫자를 정렬하면 순서를 오름차순으로 확인할 수 있습니다.

Set Lookup: array_flip을 사용하면 $nums를 키로 사용하여 $numSet에 대해 집합과 유사한 구조가 생성되므로 빠른 존재 확인이 가능합니다.

각 숫자를 반복: 숫자의 각 숫자에 대해 현재 숫자의 제곱이 세트에 있는지 확인하세요. 그렇다면 연속 행진을 계속하십시오. 그렇지 않으면 연속을 끊고 가장 긴 것이 발견되었는지 확인하세요.



  
  
  복잡성 분석




시간 복잡도: 정렬로 인한 O(n log n), 여기서 n은 요소 수입니다. 숫자로. 후속 조회 및 정사각형 줄무늬 검사는 O(n).
입니다.

공간 복잡도: O(n), 주로 집합에 숫자를 저장하는 데 사용됩니다.


이 솔루션은 가장 긴 사각형 줄무늬를 효율적으로 찾거나 유효한 줄무늬가 없으면 -1을 반환합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
        
위 내용은 배열에서 가장 긴 정사각형 줄무늬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!