⓺O H-index

Top Interview 150, leetcode medium, C++, Algorithm

Today’s code

來源

Solution1 / Brute Force Approach / 暴力解法

先排序後再做判斷

這裡就不使用sort API了，來練習insertion sort方式去排序。

然而我下面的判斷，主要是利用citations[i]的值去給index h，其實更好的做法是利用已經排序好的vector位置去做判斷。

class Solution {
public:
    int hIndex(vector<int>& citations) {
        // insertion sort
        int length = citations.size();
        int i = 1;
        int max_h = 0;
        while (i < length) {
            int start_index = 0;
            int end_index = 0;
            int j = 0;
            while (j < i) {
                if (citations[j] < citations[i]) {
                    start_index = j;
                    end_index = i;
                    break;
                }
                j++;
            }

            if (end_index) {
                int temp = citations[end_index];
                for (int i = end_index; i > start_index; i--) {
                    citations[i] = citations[i - 1];
                }
                citations[start_index] = temp;
            }
            i++;
        }

// 排序好了

        int tmp_indexh = 0;
        for(int i = 0; i < length; i++){
            if(i + 1 >= citations[i]){
                max_h = citations[i];
                break;
            }else if(citations[i] != 0){
                tmp_indexh++;
            }

        }
        if(tmp_indexh > max_h){
            max_h = tmp_indexh;
        }

        return max_h;
    }
};

Solution1 Advanced

判斷方式我們用vector的位置(position)去給值，紀錄最大的index h。

因為，當citations的值大於他的位置（position）時，目前的index h也只是他的position

我們來解釋一下，為何是position好了。首先，要知道我們是經過排序的，是一個由大到小的descending順續，所以vector的index（位置 position）也就代表了，他的index h。只要這樣我們iterate整個vector，就可以找到最大的index h。

        for(int i = 0; i < length; i++){
            if(i + 1 <= citations[i]){
                if(i + 1 > max_h){
                    max_h = i + 1;
                }
            }
        }