PHP 알고리즘을 사용하여 배열에서 K번째로 큰 값을 찾는 방법

PHP 개발에서는 배열 및 기타 작업을 정렬하고 검색해야 하는 경우가 많습니다. 배열에서 K번째로 큰 값을 찾는 것도 일반적인 문제입니다. 이 기사에서는 배열에서 K번째로 큰 값을 달성하기 위한 여러 PHP 알고리즘을 소개합니다.

1. 버블 정렬 방법

버블 정렬 방법은 이전 요소가 다음 요소보다 큰 경우 위치를 바꾸는 간단하고 이해하기 쉬운 정렬 알고리즘입니다. 이 방법의 시간 복잡도는 O(n^2)입니다.

구현 코드는 다음과 같습니다.

function bubbleSort($arr) {
  $len = count($arr);
  for ($i=0; $i<$len-1; $i++) {
    for ($j=0; $j<$len-$i-1; $j++) {
      if ($arr[$j] > $arr[$j+1]) {
        $temp = $arr[$j];
        $arr[$j] = $arr[$j+1];
        $arr[$j+1] = $temp;
      }
    }
  }
  return $arr;
}

function findKthLargest($nums, $k) {
  $nums = bubbleSort($nums);
  $len = count($nums);
  return $nums[$len-$k];
}

2. 빠른 정렬 방법

빠른 정렬 방법은 배열에서 벤치마크 요소를 선택하고 벤치마크 요소보다 작은 요소를 배치하는 것이 기본 아이디어입니다. 벤치마크 요소보다 큰 요소는 왼쪽에 배치하고 요소는 오른쪽에 배치하며 왼쪽과 오른쪽 범위를 재귀적으로 정렬합니다. 이 방법의 시간복잡도는 O(nlogn)이다.

구현 코드는 다음과 같습니다.

function quickSort($arr) {
  $len = count($arr);
  if ($len <= 1) {
    return $arr;
  }
  $pivot = $arr[0];
  $left = [];
  $right = [];
  for ($i=1; $i<$len; $i++) {
    if ($arr[$i] < $pivot) {
      $left[] = $arr[$i];
    } else {
      $right[] = $arr[$i];
    }
  }
  return array_merge(quickSort($left), [$pivot], quickSort($right));
}

function findKthLargest($nums, $k) {
  $nums = quickSort($nums);
  $len = count($nums);
  return $nums[$len-$k];
}

3. 힙 정렬 방법

힙 정렬 방법은 순서가 지정되지 않은 시퀀스를 힙으로 구성하고 순차적으로 최대값을 꺼내는 것입니다. 값을 힙 상단에 배치한 다음 순서가 지정되지 않은 나머지 시퀀스를 힙으로 재구성하는 방식으로 정렬될 때까지 계속됩니다. 이 방법의 시간복잡도는 O(nlogn)이다.

구현 코드는 다음과 같습니다.

function heapSort($arr) {
  $len = count($arr);
  for ($i=floor($len/2)-1; $i>=0; $i--) {
    adjustHeap($arr, $i, $len);
  }
  for ($j=$len-1; $j>0; $j--) {
    swap($arr, 0, $j);
    adjustHeap($arr, 0, $j);
  }
  return $arr;
}

function adjustHeap(&$arr, $i, $len) {
  $temp = $arr[$i];
  for ($k=$i*2+1; $k<$len; $k=$k*2+1) {
    if ($k+1 < $len && $arr[$k] < $arr[$k+1]) {
      $k++;
    }
    if ($arr[$k] > $temp) {
      $arr[$i] = $arr[$k];
      $i = $k;
    } else {
      break;
    }
  }
  $arr[$i] = $temp;
}

function swap(&$arr, $i, $j) {
  $temp = $arr[$i];
  $arr[$i] = $arr[$j];
  $arr[$j] = $temp;
}

function findKthLargest($nums, $k) {
  $nums = heapSort($nums);
  $len = count($nums);
  return $nums[$len-$k];
}

위는 배열에서 K번째로 큰 값을 해결하기 위한 세 가지 일반적인 PHP 알고리즘입니다. 실제 적용에서는 효율성을 보장하기 위해 실제 상황에 따라 적절한 알고리즘을 선택해야 합니다.

위 내용은 PHP 알고리즘을 사용하여 배열에서 K번째로 큰 값을 찾는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!