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] << ' ';

   return 0;
}

출력

1.5 4 6 4 1.5 7 4

이 프로그램의 시간 복잡도는 O(N*N)입니다. 여기서 N은 현재 주어진 배열의 크기입니다. 보시다시피 시간 복잡도가 좋지 않으므로 더 높은 제약 조건에서 잘 작동하도록 효율성을 높일 것입니다.

효율적인 접근

이 접근 방식에서 우리는 새로운 배열을 가져와서 배열이 정렬될 때 정렬할 것입니다. 이제 동일한 순위의 모든 요소가 함께 있을 것이라는 것을 알고 있으므로 이제 평소와 같이 순위를 매긴 다음 배열의 순위를 계산합니다. 특정 요소.

예시

#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;
}

출력

1.5 3.5 6 3.5 1.5 7 5

위 코드 설명

이 접근 방식에서는 배열을 정렬한 다음 각 요소의 순위를 시작(1부터 시작)부터 시작합니다. 이제 prev 요소가 현재 요소와 같으면 s를 늘리고 순위 합계까지 누적합니다. 요소가 변경되면 순위를 이전 요소로 나누고 전체를 새로 고치고 코드를 계속 진행합니다.

결론

이 기사에서는 배열의 모든 요소의 순위를 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식( Normal 및 Efficient)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.