A non-empty zero-indexed array A consisting
of N integers and sorted in a non-decreasing order is given. The leader of this
array is the value that occurs in more than half of the elements of A.
You are given an implementation of a
function:
class Solution { public int solution(int[]
A); }
that, given a non-empty zero-indexed array
A consisting of N integers, sorted in a non-decreasing order, returns the
leader of array A. The function should return −1 if array A does
not contain a leader.
For example, given array A consisting of
ten elements such that:
A[0] = 2
A[1] = 2
A[2] = 2
A[3]
= 2
A[4] = 2
A[5] = 3
A[6] = 4
A[7] = 4
A[8] = 4
A[9] = 6
the function should return −1, because the
value that occurs most frequently in the array, 2, occurs five times, and 5 is
not more than half of 10.
Given array A consisting of five elements
such that:
A[0] = 1
A[1] = 1
A[2] = 1
A[3] = 1
A[4] = 50
the function should return 1.
Unfortunately, despite the fact that the
function may return expected result for the example input, there is a bug in
the implementation, which may produce incorrect results for other inputs. Find
the bug and correct it. You should modify at most three lines of code.
Assume that:
N is an integer within the range
[1..100,000];
each element of array A is an integer within
the range [0..2147483647];
array A is sorted in non-decreasing order.
Complexity:
expected worst-case time complexity is
O(N);
expected worst-case space complexity is
O(N), beyond input storage (not counting the storage required for input
arguments).
Elements of input arrays can be modified.
initial code
int solution(int[] A) {
int n = A.length;
int[] L = new int[n + 1];
L[0] = -1;
for (int i = 0; i < n; i++) {
L[i + 1] = A[i];
}
int count = 0;
int pos = (n + 1) / 2;
int candidate = L[pos];
for (int i = 1; i <= n; i++) {
if (L[i] == candidate)
count = count + 1;
}
if (count > pos)
return candidate;
return (-1);
}
=> answer 100/100 드디어 100점이 나오다.
import java.util.*;
class Solution {
int solution(int[] A) {
int n = A.length;
int[] L = new int[n + 1];
L[0] = -1;
for (int i = 0; i < n; i++) {
L[i + 1] = A[i];
}
int count = 0;
int pos = (n + 1) / 2;
int candidate = L[pos];
for (int i = 1; i <= n; i++) {
if (L[i] == candidate)
count = count + 1;
}
if (n%2==0 ? count > pos : count > pos -1) // <===========
return candidate;
return (-1);
}
}
RECENT COMMENT