Здравствуйте, scf, Вы писали:

scf>Есть два множества с парами ключ-значение, где ключ неуникален, а значение числовое.

scf>Если оба множества объединить в одно, посчитать среднее арифметическое по ключу, отсортировать получившиеся ключи по среднему арифметическому и взять первые 100 строк, то мы получим 100 ключей с максимальным средним.

scf>Вопрос: как найти эти ключи или хотя бы кандидатоов на эти ключи, не считая среднее по всем ключам?

Во-первых, два множества лишние; и средние арифметические тоже лишние.

Есть множестово чисел (сколько, кстати? миллион? миллиард?). Из них нужно выбрать 100 самых больших, не читая всех чисел.
Это невозможно, в смысле, невозможно получить точное решение. В общем случае нельзя точно найти 100 максимальных элементов массива (несортированного массива), не прочитав всего массива.

Если сгодится приближенное, можно пересмотреть, скажем, случайно выбранные каждое десятое число; выбрать из них 10 маскимальных, и взять их по 10 копий каждого, чтобы получить 100 приблизительых результатов. При этом не гарантируется, что в исходном массиве на самом деле есть эти числа, но, смотря какая задача, может и подойдёт.