누락된 관측값 찾기

2028. 누락된 관찰 찾기

난이도:중

주제: 배열, 수학, 시뮬레이션

n + m 6면개의 관측치가 있으며 각 면에 1부터 6까지의 번호가 매겨져 있습니다. 관측치 중 n개가 사라졌고 m개의 관측치만 있습니다. 다행히도 n + m 롤의 평균값도 계산해 주셨습니다.

길이가 m인 정수 배열 롤이 주어졌습니다. 여기서 롤[i]는 i^번째 관측값입니다. 또한 두 개의 정수 평균과 n이 제공됩니다.

n + m 롤의 평균값이 정확히 평균이 되는 누락된 관측값을 포함하는 길이 n의 배열을 반환합니다. 유효한 답변이 여러 개 있으면 그 중 하나를 반환합니다. 해당 배열이 없으면 빈 배열을 반환합니다.

k개의 숫자 집합의

평균값은 숫자의 합을 k로 나눈 값입니다.

참고 평균은 정수이므로 n + mroll의 합은 n + m으로 나누어져야 합니다.

예 1:

• 입력: 롤 = [3,2,4,3], 평균 = 4, n = 2
• 출력: [6,6]
• 설명: 모든 n + m 롤의 평균은 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4입니다.

예 2:

• 입력: 롤 = [1,5,6], 평균 = 3, n = 4
• 출력: [2,3,2,2]
• 설명: 모든 n + m 롤의 평균은 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3입니다.

예 3:

• 입력: 롤 = [1,2,3,4], 평균 = 6, n = 4
• 출력: []
• 설명: 빠진 4개의 롤이 무엇이든 평균이 6이 되는 것은 불가능합니다.

제약조건:

m == 롤.길이
1 5 1 <= 롤[i], 평균 <= 6

힌트:

n개 롤의 합은 얼마가 되어야 할까요?
각 요소가 1에서 6 사이인 n 크기의 배열을 생성할 수 있나요?

해결책:

모든 n + m 주사위 굴림의 평균이 정확히 평균과 같도록 누락된 굴림의 배열을 결정해야 합니다. 솔루션의 단계별 분석은 다음과 같습니다.

접근 단계:

1. n + m 롤의 총합을 계산합니다. n + m 롤의 평균값이 평균이라고 가정하면 모든 롤의 총합은 total_sum = (n + m) * 평균이 되어야 합니다.
   

2. 누락된 합계 확인: m개 롤의 합은 이미 알려져 있습니다. 따라서 누락된 n개 롤의 합은 다음과 같습니다.
   
   

   missing_sum = total_sum - ∑(rolls)

여기서 ∑(롤)은 롤 배열 요소의 합입니다.

1. 타당성 확인: 각 굴림은 6면 주사위이므로 누락된 값은 1에서 6(포함) 사이여야 합니다. 따라서 누락된 n개 롤의 합은 다음 사이에 있어야 합니다.

   min_sum = n X 1 = n

그리고

   max_sum = n X 6 = 6n

missing_sum이 이 범위를 벗어나면 유효한 누락 관측치를 구성하는 것이 불가능하며 빈 배열을 반환해야 합니다.

1. 누락된 합계를 분배합니다. missing_sum이 유효하면 처음에 각 요소를 1(가능한 최소값)로 채워서 n개의 롤에 배포합니다. 그런 다음 필요한 Missing_sum에 도달할 때까지 요소를 1에서 6까지 증가시킵니다.

이 솔루션을 PHP로 구현해 보겠습니다:

2028. 누락된 관찰값 찾기

  
  
  설명:






입력:


롤 = [3, 2, 4, 3]

평균 = 4

n = 2





단계:


총 롤 수는 n + m = 6입니다.

필요한 총 합은 6 * 4 = 24입니다.

주어진 롤의 합은 3 + 2 + 4 + 3 = 12입니다.

누락된 롤에 필요한 합은 24 - 12 = 12입니다.





합계가 12가 되는 두 개의 누락된 롤이 필요하며 유일한 가능성은 [6, 6]입니다.




결과:


예 1: 출력은 [6, 6]입니다.

예 2: 출력은 [2, 3, 2, 2]입니다.

예 3: 유효한 솔루션이 없으므로 출력은 []입니다.






  
  
  시간 복잡도:



롤의 합을 계산하는 데는 O(m)이 걸리고, Missing_sum을 분배하는 데는 O(n)이 걸립니다. 따라서 전체 시간 복잡도는 
O(n + m)이며 이는 입력 제약 조건에 효율적입니다.


이 솔루션을 사용하면 유효한 누락 롤을 찾거나 솔루션이 없을 때 빈 배열을 반환할 수 있습니다.



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

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


링크드인
깃허브



          

            
        
위 내용은 누락된 관측값 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!