0
배열 arr[]={2,4,5,7,8,12,16,18,20}을 정렬했습니다.정렬 된 배열 및 복잡도가있는 합계 찾기 O (n)
덧셈이 12이고 복소수가 O(n) 인 요소 쌍을 찾아야합니다.
아무도 도와 줄 수 있습니까?
A
답변
2
당신이 불행하게도, 단지 몇 가지가 올바른 방향으로 당신을지도한다 생각하는 해결책 : 마음에
지키는 배열이 정렬되어, 해당 다음 중?
arr[x+1] + arr[y] < arr[x] + arr[y]
or arr[x+1] + arr[y] > arr[x] + arr[y]
arr[x] + arr[y-1] < arr[x] + arr[y]
or arr[x] + arr[y-1] > arr[x] + arr[y]
이들에 대한 답변을 충분히 생각하면 (그리고 어쩌면 그릴 수도 있음) 해결 방법을 따라야합니다. 시작하는 방법에 대한
힌트 :
하자 X = 0, Y = N-1.
...
1
이것을 시도 : 배열이 정렬되므로
는 제 1 엘리먼트의 총합을 (도착 [0]) 및 마지막 엘리먼트 (도착 [8]). 합이 12보다 큰 경우 합계를 낮춰야하므로 가장 큰 숫자를 다음으로 큰 숫자 (이 경우 arr [7])로 바꿉니다. 합이 12보다 작 으면 합계를 늘려야하므로 가장 작은 숫자를 다음 작은 숫자로 바꿉니다 (이 경우 arr [0]을 arr [1]로 바꿉니다). 원하는 합계를 얻을 때까지이 프로세스를 계속 반복하거나 합계 한 두 숫자가 배열의 동일한 색인에있는 경우입니다.
이것은 잘못된 질문입니다. 복잡성은 가능한 입력 집합에 대한 문제를 나타냅니다. 이 경우 문제에 대한 언급 된 고정 된 입력이 있습니다. 또한 이것은 숙제 문제처럼 들립니다. 이 경우 숙제로 표시하십시오. 마지막으로, 당신은 명확한 질문을하지 않고 있습니다. 뭘 원하는거야? 얼마만큼의 도움과 방향? – Kaganar
아니요, 숙제로 아무것도 태그하지 마십시오. 해당 태그는 현재 사용되지 않습니다. –
운동은 CLRS에서 거의 확실하게 중복됩니다. –