Daily Retcode Challenge – 540. 정렬된 배열의 단일 요소
문제 조건이 logn이므로 이진 검색측 알고리즘으로 보입니다. 바이너리 검색이니까 반으로 줄여야 할 것 같습니다. 또한 문제 조건의 nums.size()는 1보다 크거나 같은 홀수입니다.
다음으로 기본 사례에 대해 생각했습니다.
len == 1인 기본 사례: 나머지 요소가 답입니다.
len == 3인 경우 기본 사례: 하나를 선택하고 반환합니다.
If len == 5: 이등분해야 하기 때문에 2 또는 3으로 나눈다고 가정해 봅시다. 그러면 다음 두 가지 경우가 발생합니다.
- 중간 시작점 왼쪽에 요소가 있는 경우. 나. (1, 2 / 2 / 3, 3)
- 중간 시작점 오른쪽에 요소가 있는 경우. 나. (2, 2 / 3 / 3, 4)
If len == 7: 이등분, 3과 4를 같은 방식으로 생각해 봅시다.
- (2, 2, 3 / 3 / 4, 4, 5)와 같이 왼쪽에 요소가 있는 경우
- (1, 2, 2 / 3 / 3, 4, 4)와 같이 오른쪽에 요소가 있는 경우
숫자가 반드시 홀수인 상황에서는 1이 포함된 숫자를 찾는 것이 가능해 보입니다. 그걸 어떻게 찾나요… 고민 끝에. 짝수인지 홀수인지에 따라 검색 범위의 반쪽 개수가 달라진다는 사실을 깨달았습니다.
- 가운데는 이전과 동일 + 가운데 인덱스는 짝수 -> 가운데 뒤는 버릴 수 있음( 짝수 개의 항목 버려짐)
- (xxx)xx
- 중간이 전과 동일 + 중간 지수가 홀수 -> 중간 뒤를 주목해야 함 (짝수의 항목은 폐기됩니다)
- xxxx (xxx)
- 중간은 다음과 동일 + 중간 색인은 짝수 -> 중간 앞의 것은 버릴 수 있음 (짝수의 항목은 폐기됩니다)
- xx(xxx)
- 가운데는 뒤와 같음 + 가운데 지수가 홀수 -> 가운데 앞을 주목해야 함 (짝수의 항목은 폐기됩니다)
- (xxx)xxxx
이것을 반복해서 반복할 수 있습니다. 이것은 len == 3에도 적용됩니다. 항상 짝수 개의 요소를 버리기 때문에 알고리즘이 항상 홀수 개의 목록을 통해 실행된다는 것을 알 수 있습니다. 이에 대한 구현은 다음과 같습니다.
예외적으로 nums(middle)가 앞뒤와 많이 다른 경우는 생각하지 못했습니다. 이 경우 중간이 답입니다. + 가능하면 종료 조건을 먼저 넣으세요.
// runtime 31ms, beats 49.25%
// memory 22.3MB, beats 62.74%
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
if(nums.size() == 1) return nums(0);
int start = 0; // 시작 index
int end = nums.size() - 1; // 끝 index
int middle; // 가운데 index
while(end != start){ // 길이가 1이 될 때까지 반복
middle = (start + end) / 2;
// 실수 : 이 경우를 생각하지 못했음
if(nums(middle) != nums(middle -1) && nums(middle) != nums(middle + 1)) return nums(middle);
else if(nums(middle) == nums(middle -1)){
if(middle % 2){
start = middle + 1;
}
else{
end = middle;
}
}
else { // nums(middle) == nums(middle + 1)
if(middle % 2){
end = middle - 1;
}
else{
start = middle;
}
}
}
return nums(start);
}
};
지금은 어떻게 개선할 수 있을지…
// runtime 16ms, beats 99.39%
// memory 22.3MB, beats 62.74%
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
if(nums.size() == 1) return nums(0);
int start = 0; // 시작 index
int end = nums.size() - 1; // 끝 index
int middle; // 가운데 index
while(end != start){ // 길이가 1이 될 때까지 반복
middle = (start + end) / 2;
if(nums(middle) != nums(middle -1) && nums(middle) != nums(middle + 1)) return nums(middle);
else if(nums(middle) == nums(middle -1)){
if(middle % 2){
start = middle + 1;
}
else{
end = middle - 2; // middle과 middle-1은 같은 수이므로 middle-2로 갱신
}
}
else { // nums(middle) == nums(middle + 1)
if(middle % 2){
end = middle - 1;
}
else{
start = middle + 2; // middle과 middle+1은 같은 수이므로 middle+2로 갱신
}
}
}
return nums(start);
}
};검색 범위를 몇 번 더 좁히는 것으로 충분합니다. 두 개의 조각이 붙는 부분을 작게 만들어 퀘스트의 크기를 확실히 2개 줄였습니다. 모든 경우에 해당한다고 가정하면 검색 범위는 약 50%의 확률로 2로 주어진다.