배열을 정렬할 수 있는지 확인

3011. 배열을 정렬할 수 있는지 확인

난이도:중

주제: 배열, 비트 조작, 정렬

양수 정수 숫자의 색인이 0인 배열이 제공됩니다.

한 번의 작업에서 두 개의 인접 요소가 동일한 세트 비트 수¹인 경우 교체할 수 있습니다. 이 작업은 얼마나 횟수만큼 수행할 수 있습니다(0개 포함).

배열을 정렬할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

예 1:

• 입력: 숫자 = [8,4,2,30,15]
• 출력: true
• 설명: 모든 요소의 이진 표현을 살펴보겠습니다. 숫자 2, 4, 8에는 각각 이진수 표현이 "10", "100", "1000"인 하나의 세트 비트가 있습니다. 숫자 15와 30에는 각각 이진 표현 "1111"과 "11110"을 갖는 4개의 세트 비트가 있습니다. 4가지 작업을 사용하여 배열을 정렬할 수 있습니다.
  • 숫자[0]을 숫자[1]로 바꿉니다. 이 연산은 8과 4가 각각 하나의 세트 비트를 갖기 때문에 유효합니다. 배열은 [4,8,2,30,15]가 됩니다.
  • 숫자[1]을 숫자[2]로 바꿉니다. 이 연산은 8과 2가 각각 하나의 세트 비트를 갖기 때문에 유효합니다. 배열은 [4,2,8,30,15]가 됩니다.
  • 숫자[0]을 숫자[1]로 바꿉니다. 이 연산은 4와 2가 각각 하나의 세트 비트를 갖기 때문에 유효합니다. 배열은 [2,4,8,30,15]가 됩니다.
  • 숫자[3]을 숫자[4]로 바꿉니다. 30과 15에는 각각 4개의 세트 비트가 있으므로 이 연산은 유효합니다. 배열은 [2,4,8,15,30]이 됩니다.
  • 배열이 정렬되었으므로 true를 반환합니다.
  • 배열을 정렬하는 다른 작업 순서도 있을 수 있습니다.

예 2:

• 입력: 숫자 = [1,2,3,4,5]
• 출력: true
• 설명: 배열이 이미 정렬되어 있으므로 true를 반환합니다.

예 3:

• 입력: 숫자 = [3,16,8,4,2]
• 출력: false
• 설명: 여러 연산을 사용하여 입력 배열을 정렬하는 것이 불가능하다는 것을 알 수 있습니다.

예 4:

• 입력: 숫자 = [75,34,30]
• 출력: false
• 설명: 여러 연산을 사용하여 입력 배열을 정렬하는 것이 불가능하다는 것을 알 수 있습니다.

제약조건:

• 1 <= nums.length <= 100
• 1 <= 숫자[i] <= 2⁸

힌트:

1. 배열을 세그먼트로 분할합니다. 각 세그먼트에는 동일한 수의 세트 비트를 가진 연속 요소가 포함되어 있습니다.
2. 왼쪽에서 오른쪽으로 이전 세그먼트의 가장 큰 요소는 현재 세그먼트의 가장 작은 요소보다 작아야 합니다.

해결책:

이진 표현에서 설정된 비트 수가 동일한 인접한 요소만 교체하여 배열을 정렬할 수 있는지 확인해야 합니다. 계획은 다음과 같습니다.

해결 단계:

1. 키 관찰: 이 작업을 사용하면 설정된 비트 수가 동일한 경우에만 인접한 요소를 교체할 수 있습니다. 이렇게 하면 설정된 비트 수가 다른 요소 간 교체가 제한됩니다.

2. 계획:

   • 바이너리 표현에서 설정된 비트 수를 기준으로 요소를 그룹화합니다.
   • 그룹 내에서 요소를 교체하여 재배열할 수 있으므로 각 그룹을 개별적으로 정렬하세요.
   • 각 그룹을 정렬한 후 정렬된 그룹을 다시 병합하세요.
   • 병합된 배열이 정렬되어 있는지 확인하세요. 그렇다면 허용된 연산을 사용하여 배열을 정렬하는 것이 가능합니다.

3. 단계:

   • 동일한 설정 비트 수로 각 번호와 그룹 번호의 설정 비트를 계산합니다.
   • 각 그룹을 개별적으로 정렬합니다.
   • 정렬된 그룹에서 배열을 재구성하고 결과가 정렬되었는지 확인합니다.

이 솔루션을 PHP로 구현해 보겠습니다. 3011. 배열을 정렬할 수 있는지 확인

  
  
  설명:




countSetBits 함수: 비트 연산을 사용하여 숫자에 설정된 비트 수를 셉니다.

요소 그룹화: bitGroups는 각 키가 설정된 비트 수를 나타내고 각 값이 해당 개수의 설정된 비트를 포함하는 숫자 배열인 연관 배열입니다.

정렬 및 재구성:


설정된 비트 수에 따라 요소를 그룹화하기 위해 숫자를 반복합니다.
각 그룹을 독립적으로 정렬합니다.
그런 다음 정렬된 각 그룹 요소를 원래 순서대로 삽입하여 배열을 재구성합니다.
마지막으로 재구성된 배열이 내림차순으로 정렬되어 있는지 확인합니다. 그렇다면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.


최종 비교: 재구성된 배열을 완전히 정렬된 버전의 nums와 비교합니다. 일치하면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.



  
  
  복잡성 분석




시간 복잡도: O(n log n) 각 그룹 내 정렬 및 최종 비교로 인해 

공간 복잡도: O(n) 비트 그룹을 저장하는 데 사용됩니다.


이 솔루션을 사용하면 동일한 비트 수로 인접한 요소만 교체하여 가능한 경우 정렬된 순서를 달성할 수 있습니다.

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

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


링크드인
깃허브








세트 비트 세트 비트는 값이 1인 숫자를 이진수로 표현한 비트를 의미합니다. ↩





          

            
  

            
        
위 내용은 배열을 정렬할 수 있는지 확인의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!