My 2 C++ solutions (sorting based O(NlogN) and counting based O(N))


  • 0
    D
    1. Counting-based, first using an array O(N) to count how many papers have citation of i (for count[len], it is the number of the papers that have citations no less than len). Then scan the count array to calculate how many papers have citations no less than i (i.e. count[i]+=count[i+1]) and check if it meests the h-index criterion (i.e. count[i] >= i)

      class Solution {
      public:
      int hIndex(vector<int>& citations) {
      int len = citations.size(), i;
      vector<int> count(len+1, 0);
      for(i=0; i<len; ++i) citations[i] >=len?++count[len]:++count[citations[i]];
      for(i=len; i>0 && count[i]<i; --i, count[i]+=count[i+1]);
      return i;
      }
      };

    2. Sorting based solution, it is straightforward

      class Solution {
      public:
      int hIndex(vector<int>& citations) {
      int res = 0, len = citations.size(), i;
      std::sort(citations.begin(), citations.end());
      for(i=len-1; i>=0 && citations[i]>=(len-i); --i);
      return len-i-1;
      }
      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.