Как найти K-ю наименьшую сумму в отсортированной матрице MxN

Question

Я видел решения о том, как найти наименьший K-й элемент в отсортированной матрице, и я также видел решения о том, как найти наименьшую K-ю сумму в двух массивах.

Но недавно я нашел вопрос, в котором предлагается найти наименьшую K-ю сумму в отсортированной матрице MxN. Сумма должна состоять из одного элемента из каждой строки. Я действительно изо всех сил пытаюсь разработать что-нибудь, близкое к рабочему решению, не говоря уже о грубой силе. Любая помощь будет принята с благодарностью!

Я думал, что это будет какая-то куча проблем ... Но, возможно, это проблема с графиком? Я не очень хорош с графиками.

Answer 1

или в каждой строке мы вычисляем все возможные суммы, но оставляем k наименьшим. Мы можем использовать быстрый выбор, чтобы сделать это за линейное время.

Сложность ниже должна быть: O (n * m * k).

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        vector<int> sums = { 0 }, cur = {};

        for (const auto& row : mat) {
            for (const int cel : row) {
                for (const int sum : sums) {
                    cur.push_back(cel + sum);
                }
            }

            int nth = min((int ) cur.size(), k);

            nth_element(cur.begin(), cur.begin() + nth, cur.end());

            sums.clear();
            copy(cur.begin(), cur.begin() + nth, back_inserter(sums));
            cur.clear();
        }

        return *max_element(sums.begin(), sums.end());
    }
};

Answer 2

Я предполагаю, что "отсортированная матрица MxN" означает, что каждая строка матрицы отсортирована. Если вы уже знаете, как объединить 2 строки и взять только первые K элементов, вы можете выполнить ту же процедуру, чтобы объединить все строки матрицы. Игнорируйте преобразование Java между int [] и List, следующий код должен работать.

class Solution {

/**
 * Runtime O(m * k * logk)
 */ 
public int kthSmallest(int[][] mat, int k) {
    List<Integer> row = IntStream.of(mat[0]).boxed().collect(Collectors.toList());
    for (int i = 1; i < mat.length; i++) {
        row = kthSmallestPairs(row, mat[i], k);
    }
    return row.get(k - 1);
}

/**
 * A pair is formed from one num of n1 and one num of n2. Find the k-th smallest sum of these pairs
 * Queue size is maxed at k, hence this method run O(k logk)
 */
List<Integer> kthSmallestPairs(List<Integer> n1, int[] n2, int k) {
    // 0 is n1's num,     1 is n2's num,     2 is n2's index
    Queue<int[]> que = new PriorityQueue<>((a, b) -> a[0] + a[1] - b[0] - b[1]);

    // first pair each num in n1 with the 0-th num of n2. Don't need to do more than k elements because those greater
    // elements will never have a chance
    for (int i = 0; i < n1.size() && i < k; i++) {
        que.add(new int[] {n1.get(i), n2[0], 0});
    }

    List<Integer> res = new ArrayList<>();
    while (!que.isEmpty() && k-- > 0) {
        int[] top = que.remove();
        res.add(top[0] + top[1]);
        // index of n2 is top[2]
        if (top[2] < n2.length - 1) {
            int nextN2Idx = top[2] + 1;
            que.add(new int[] {top[0], n2[nextN2Idx], nextN2Idx});
        }
    }

    return res;
}

}

Answer 3

Вы можете создать приоритетную очередь minHeap и сохранить в ней суммы и соответствующий индекс строк. Затем, как только вы наберете наименьшую сумму, вы можете проверить следующих кандидатов на наименьшую сумму, увеличив индекс каждой строки на единицу.
Вот структуры данных, которые вам понадобятся.

typedef pair<int,vector<int>> pi;
priority_queue<pi,vector<pi>,greater<pi>> pq;

Вы можете попробовать вопрос сейчас, для справки. Я также добавил код, который я написал для этой проблемы.

typedef pair<int,vector<int>> pi;

int kthSmallest(vector<vector<int>>& mat, int k) {
    int m=mat.size();
    int n=mat[0].size();
    priority_queue<pi,vector<pi>,greater<pi>> pq;
    int sum=0;
    for(int i=0;i<m;i++)
        sum+=mat[i][0];
    vector<int> v;
    for(int i=0;i<m;i++)
        v.push_back(0);
    pq.push({sum,v});
    int count=1;
    int ans=sum;
    unordered_map<string,int> meep;
    string s;
    for(int i=0;i<m;i++)
        s+="0";
    meep[s]=1;
    while(count<=k)
    {
        ans=pq.top().first;
        v=pq.top().second;
        // cout<<ans<<endl;
        // for(int i=0;i<v.size();i++)
        //     cout<<v[i]<<" ";
        // cout<<endl;
        pq.pop();
        for(int i=0;i<m;i++)
        {
            vector<int> temp;
            sum=0;
            int flag=0;
            string luuul;
            for(int j=0;j<m;j++)
            {
                if(i==j&&v[j]<n-1)
                {
                    sum+=mat[j][v[j]+1];
                    temp.push_back(v[j]+1);
                    luuul+=to_string(v[j]+1);
                }
                else if(i==j&&v[j]==n-1)
                {
                    flag=1;
                    break;
                }
                else
                {
                    sum+=mat[j][v[j]];
                    temp.push_back(v[j]);
                    luuul+=to_string(v[j]);
                }
            }
            if(!flag)
            {
                if(meep[luuul]==0)
                    pq.push({sum,temp});
                meep[luuul]=1;
            }
        }
        // cout<<endl;
        count++;
    }
    return ans;
}