With and without sort() Java AC solution


  • 1

    Below is using sort(). The idea is actually the same with no sort() solution. The most significant disadvantage I think is not the time performance, is the if statement, I tried many times to pass all the test cases.....

    public int hIndex(int[] c) {
            if (c.length == 0) return 0;
            int len = c.length;
            Arrays.sort(c);
            
            int count = 0;
            int h = 1;
            
            for (int i = len - 1; i >= 0; i--) {
                h = c[i];
                count++;
                if (count == h) return h;
                if (count > h && count > 1) return Math.min(count - 1, c[i + 1]);
                if (count == 1 && count > h) return 0;
            }
            return count;
        }
    

    Without sort(), this method actually also sorts (not real sort, but kind of sort) the citation, just by ourselves instead of sort().

    public int hIndex(int[] c) {
            int n = c.length;
            if (n == 0) return 0;
            
            // the number of high citations
            int[] record = new int[n + 1];
            
            // count the citations
            for (int i : c) {
                if (i >= n) record[n]++;
                else record[i]++;
            }
            
            // get the h
            int count = 0;
            for (int i = n; i > 0; i--) {
                count += record[i];
                if (count >= i) {
                    return i;
                } 
            }
            return 0;
        }
    

Log in to reply
 

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