배열에서 가장 큰 숫자 찾기

오늘은 정렬되지 않은 배열에서 가장 큰 수를 찾는 방법을 살펴보겠습니다.

다른 솔루션을 볼 수 있습니다

두 개의 for 루프 사용

최대 변수 사용

기본 제공 정렬 사용

두 가지 for 루프 방법을 살펴보겠습니다.

int findLargestNumber(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      boolean flag = true;
      for (int j = 0; j < arr.length; j++) {
        if (arr[j] > arr[i]) {
          flag = false;
          break;
        }
      }
      if (flag) {
        return arr[i];
      }
    }
    return -1;
  }

여기서 우리는 배열을 arr로 사용합니다.
0부터 배열 길이(arr.length)까지 for 루프를 만들 것입니다.

i 루프에서 먼저 인덱스 i의 요소를 배열의 가장 큰 요소로 간주하므로 flag를 true로 설정합니다.

이제 j 루프에서 인덱스 i에 있는 요소보다 큰 요소가 있는지 확인할 것입니다.

true이면 플래그를 false로 설정하여 루프를 중단합니다.

플래그가 false이기 때문에 if 블록에 들어가지 않고 i가 다음 인덱스로 이동될 것입니다. 이것은 i가 가장 큰 요소를 가리킬 때 배열에서 가장 큰 요소로 이동할 때까지 발생합니다. j 루프는 플래그를 false로 설정하지 않습니다. if 블록에 들어가 가장 큰 요소를 반환합니다.

시간 복잡도 O(n2)

이제 O(n)을 만드는 방법을 살펴보겠습니다.

int findLargestNumber2(int arr[]) {
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
      if (max < arr[i]) {
        max = arr[i];
      }
    }
    return max;
  }

이 방법에서는 변수max를 선언하고 Integer.MIN_VALUE(-2147483648)로 초기화합니다.

이제 우리는 for 루프를 사용하여 배열을 반복하고 현재 최대값보다 큰지 확인합니다. 참이면 해당 값을 최대값에 할당하고 루프가 종료되면 최대값을 반환합니다.

시간 복잡도:- O(n)

새로운 내장 정렬 방법을 사용하여 보자

int findLargestNumber3(int[] arr){
    Arrays.sort(arr);
    return arr[arr.length-1];
  }

여기에서 우리는 Java 내장 int Arrays.sort() 메서드를 사용하고 있습니다. 이 메서드는 우리를 오름차순으로 정렬하므로 마지막에 표시될 가장 큰 요소를 가져와야 하는 경우 arr[arr.length-1]를 사용하여 액세스할 수 있습니다. 이 방법을 사용하여 인덱스 값을 변경하여 두 번째로 큰 요소, 첫 번째로 작은 요소, 두 번째로 작은 요소, n개의 가장 큰 요소 또는 가장 작은 요소를 찾습니다.

시간 복잡도:- O(n log n)

Note:- Arrays.sort() uses As of Java 8, Arrays.sort uses two sorting algorithms. One is a modification of Quicksort named dual-pivot quicksort, the other an adaptation of MergeSort named Timsort. Both have a time complexity of O(n log n)

이것은 내 DSA 준비 시리즈의 일부입니다.
Day 1 to 9 : 알고리즘 분석
10일:
11일차:
12일차: 배열 기본 사항
13일: