>백엔드 개발 >C++ >C++로 작성된 배열 요소 정렬 순위

C++로 작성된 배열 요소 정렬 순위

王林
王林앞으로
2023-08-26 22:45:121325검색

C++로 작성된 배열 요소 정렬 순위

주어진 문제에서 우리는 배열의 모든 주어진 요소의 순위를 매겨야 하며 가장 작은 숫자가 가장 작은 순위를 갖고 가장 큰 숫자가 가장 큰 순위를 갖습니다. 예를 들어, 빈도에 따라 숫자의 순위도 변경해야 합니다. -

Input : 20 30 10
Output : 2.0 3.0 1.0

Input : 10 12 15 12 10 25 12
Output : 1.5, 4.0, 6.0, 4.0, 1.5, 7.0, 4.0

Here the rank of 10 is 1.5 because there are two 10s present in the given array now if we assume they both take different ranks i.e. 1 and 2 and we thus divide it within themselves so their rank becomes 1.5 and 1.5.

Input : 1, 2, 5, 2, 1, 60, 3
Output : 1.5, 3.5, 6.0, 3.5, 1.5, 7.0, 5.0

답을 찾는 방법

답을 찾는 방법에는 두 가지가 있습니다. 즉,

무차별 대입 방법

이 방법에서는 반복해서 특정 요소를 선택하고 순위를 결정합니다.

예제

#include <bits/stdc++.h>
using namespace std;

int main() {
   int arr[] = {1, 2, 5, 2, 1, 25, 2}; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our given array

   float rank[n] = {0}; // our ranking array
   for (int i = 0; i < n; i++) {
      int r = 1; // the number of elements greater than arr[i]
      int s = 1; // the number of elements equal to arr[i]

      for (int j = 0; j < n; j++) {
         if (j != i && arr[j] < arr[i])
            r += 1;
   
         if (j != i && arr[j] == arr[i])
            s += 1;
      }
      rank[i] = r + (float)(s - 1) / (float) 2; // using formula
      //to obtain rank of particular element

   }

   for (int i = 0; i < n; i++) // outputting the ranks
      cout << rank[i] << &#39; &#39;;

   return 0;
}

출력

1.5 4 6 4 1.5 7 4

이 프로그램의 시간 복잡도는 O(N*N)입니다. 여기서 N은 보시다시피 주어진 배열의 크기이므로 시간 복잡도는 좋지 않습니다. 우리는 더 높은 제약 조건에 더 잘 적응할 수 있도록 효율성을 향상시킬 것입니다.

효율적인 방법

이 방법에서는 새 배열을 가져와 정렬합니다. 배열이 정렬되었으므로 이제 동일한 순위를 가진 모든 요소가 함께 있을 것이라는 것을 알았으므로 이제 평소대로 순위를 지정하고 그런 다음 특정 요소의 순위를 계산합니다.

Example

#include <bits/stdc++.h>

using namespace std;

int main() {
   int arr[] = {1, 2, 5, 2, 1, 60, 3}; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our given array
   float rank[n] = {0}; // our ranking array
   int old[n];
   for(int i = 0; i < n; i++)
   old[i] = arr[i];
   sort(arr, arr+n); // sorting the array
   int prev = arr[0];
   int r = 1; // ranks
   int s = 0; // frequency
   int tot = 0; // will stack up all the rank contained by an element
   map<int, float> rrank;

   for (int i = 0; i < n; i++) {
      if(prev == arr[i]) {
         s++;
         tot += r;
      } else {
         float now = 0;
         now = (float)tot/s; // dividing the ranks equally
         rrank[prev] = now;
         prev = arr[i];
         tot = r;
         s = 1;
      }
      r++;
   }
   rrank[arr[n-1]] = (float)tot/s;
   for (int i = 0; i < n; i++) // outputting the ranks
      cout << rrank[old[i]] << " ";

   return 0;
}

Output

1.5 3.5 6 3.5 1.5 7 5

위 코드 설명

이 방법에서는 배열을 정렬한 후 각 요소를 처음부터 순위를 매깁니다(순위는 1부터 시작). 이제 이전 요소가 현재 요소와 같으면 s를 증가시키고 순위 합계에 추가합니다. 요소가 변경되면 이전 요소의 순위를 분리하고 s와 합계를 새로 고치고 코드를 계속 진행합니다.

결론

이 글에서는 배열에 있는 모든 요소의 순위를 찾는 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하는 완전한 방법(정상적이고 효율적인)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.

위 내용은 C++로 작성된 배열 요소 정렬 순위의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
이 기사는 tutorialspoint.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제