시간 복잡도가 O(N)인 배열에서 세 번째 최대값 찾기
2158 단어 codenewbiejavacomputerscience
비어 있지 않은 정수 배열이 주어지면 이 배열에서 세 번째 최대 수를 반환합니다. 존재하지 않으면 최대 수를 반환합니다. 시간 복잡도는 O(n)이어야 합니다.
예 1:
입력: [3, 2, 1]
출력: 1
설명: 세 번째 최대값은 1입니다.
예 2:
입력: [1, 2]
출력: 2
설명: 세 번째 최대값이 존재하지 않으므로 대신 최대값(2)이 리턴됩니다.
예 3:
입력: [2, 2, 3, 1]
출력: 1
설명: 여기서 세 번째 최대값은 세 번째 최대 고유 수를 의미합니다.
값이 2인 두 숫자는 모두 두 번째 최대값으로 간주됩니다.
JAVA의 내 솔루션은 다음과 같습니다.
class Solution{
public int thirdMax(int[] nums){
int first=nums[0],second=Integer.MIN_VALUE,third=Integer. MIN_VALUE,n=nums.length,count=0;
if(n<3)
{
if(n==1)
{
return nums[0];
}
else
{
return Math.max(nums[0],nums[1]);
}
}
for(int i=1;i<n;i++)
{
if(first<nums[i])
{
first=nums[i];
}
}
for(int i=0;i<n;i++)
{
if(first>nums[i]&&nums[i]>second)
{
second=nums[i];
}
}
for(int i=0;i<n;i++)
{
if(second>nums[i]&&nums[i]>=third)
{
third=nums[i];
count++;
}
}
if(third==Integer.MIN_VALUE)
{
if(count!=0)
{
return third;
}
third=first;
}
return third;
}
}
여기이 솔루션에서 방금 thirdMax 번호를 찾는 방법의 기능을 작성했습니다!
먼저 첫 번째(첫 번째 요소로 초기화), 두 번째, 세 번째, n(배열의 크기), count(기본적으로 하나의 중요한 테스트 케이스에 사용됨)와 같은 4개의 정수 유형 변수를 사용합니다.
최대 값을 찾아야 하므로 여기서 변수를 최소 값(두 번째 및 세 번째)으로 초기화해야 합니다. 따라서 초기화 값을 배열 요소와 비교할 수 있습니다.
그건 그렇고 당신은 질문 설명을 읽은 후에 알 것입니다!
그래서 변수 초기화 후..
첫 번째 조건이 1에서 2까지의 배열 길이에 대한 경우 반환은 최대 요소여야 합니다.
그 후 여기에 3 for 루프가 있습니다. 첫 번째 for 루프는 첫 번째 최대 번호를 찾기 위한 것입니다.
두 번째 for 루프는 두 번째 최대 번호를 찾는 것입니다.
세 번째 for 루프는 세 번째 최대 번호를 찾는 것입니다. 배열에서.
그리고 조건이 하나의 특별한 경우에 해당하는 경우, 즉 배열에 세 번째 최대 요소가 없으면 첫 번째 최대 요소를 반환합니다.
참고: 여기서 배열 요소가 Integer.MIN_VALUE 와 동일하고 세 번째 최대 요소인 경우 그대로 반환한다고 가정합니다!
나는 그것이 당신을 도울 수 있기를 바랍니다!!
이에 대해 혼란이 있으면 언제든지 의견에 질문하십시오. 설명하고 싶습니다. :)
해피코딩❤️
Reference
이 문제에 관하여(시간 복잡도가 O(N)인 배열에서 세 번째 최대값 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/suchitra_13/find-third-maximum-number-in-an-array-with-o-n-time-complexity-2ac7텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)