시간 복잡도가 O(N)인 배열에서 세 번째 최대값 찾기

질문 설명은 다음과 같습니다.

비어 있지 않은 정수 배열이 주어지면 이 배열에서 세 번째 최대 수를 반환합니다. 존재하지 않으면 최대 수를 반환합니다. 시간 복잡도는 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 와 동일하고 세 번째 최대 요소인 경우 그대로 반환한다고 가정합니다!
나는 그것이 당신을 도울 수 있기를 바랍니다!!
이에 대해 혼란이 있으면 언제든지 의견에 질문하십시오. 설명하고 싶습니다. :)

해피코딩❤️

좋은 웹페이지 즐겨찾기