static int secondLargest(int n,int arr[]){
int max=0,secondmax=-1;
for(int i=0;i<n;i++){
if (arr[i]>max){
max=arr[i];
}
}
for(int i=0;i<n;i++){
if (arr[i]<max && arr[i]>secondmax){
secondmax=arr[i];
}
}
return secondmax;
// Arrays.sort(arr);
// for(int i=1;i<n;i++){
// if (arr[n-i]!=arr[n-i-1]){
// return arr[n-i-1];
// }
// }
// return -1;
}
}
Входы могут быть следующими
6
12 35 1 10 34 1
или
10
5 5 5 5 5 5 5 5 5 5
Если я отсортирую это, это добавит больше времени к ответу
учитывая приведенные вами примеры, это не должно быть проблемой. Если вы будете отслеживать, как предложено в принятом ответе, вам нужно будет выполнить (по крайней мере) одну условную проверку для каждого элемента.
Вы можете перебирать массив и отслеживать самый большой и второй по величине элементы:
static int secondLargest(int arr[]) {
// Input sanity
if (arr == null || arr.length < 2) {
throw new IllegalArgumentException("arr must have at least two elements");
}
// Initialization
int max;
int secondmax;
if (arr[0] > arr[1]) {
max = arr[0];
secondmax = arr[1];
} else {
max = arr[1];
secondmax = arr[0];
}
// Go over the rest of the elements
for (int = 2; i < arr.length; ++i) {
int elem = arr[i];
if (elem >= max) {
secondmax = max;
max = elem;
} else if (elem > secondmax) {
secondmax = elem;
}
}
return secondmax;
}
Это имеет временную сложность O(n) и пространственную сложность O(1), где n — длина массива.
Спасибо за вашу помощь! Потребовалось немного доработать, но я нашел решение.
Я оставляю вам другое решение (сложность времени, которую я вам должен):
int max = 0, secondmax = 0;
for( int i = 0; i < n; i++ ) {
if ( arr[i] > max ) {
// "secondmax" takes the value contained in "max"
secondmax = max;
// "max" takes the value contained in "arr[i]"
max = arr[i] ;
}
else if ( arr[i] > secondmax ) {
// "secondmax" takes the value contained in "arr[i]"
secondmax = arr[i];
}
}
Время -> O(N) Пробел -> O(1)
static int secondLargest(int n,int arr[]){
int max=arr[0],secondmax=-1;
if (arr[0]>arr[1]){
max=arr[0];
secondmax=arr[1];
}
if (arr[0]<arr[1]){
max=arr[1];
secondmax=arr[0];
}
for(int i=2;i<n;i++){
if (arr[i]>max){
secondmax=max;
max=arr[i];
}
else if (arr[i]>secondmax && arr[i]<max){
secondmax=arr[i];
}
}
return secondmax;
}
}
что мешает вам отсортировать массив и поместить элементы в список, который не принимает дубликатов?