How to find kth largest sublist(by length) from a nested list-CodePudding

I have a list like this

list = [[1, 2, 3, 4], [1, 9, 12], [9], [8], [7, 8, 9, 10, 12, 16], [7, 8, 9, 10], [4, 5, 6, 7], [6, 7, 8, 9, 10, 11]]

I need to find the k-th largest sublist by length of the list from the above-nested list, a small twist is there:

If K =2 the answer should be [4,5,6,7] as it comes later in the processing
If K = 1 the answer should be [6, 7, 8, 9, 10, 11] as it comes later in the processing

I initially sorted the nested sublist by length, which I think will be useful to find kth largest sublist, as it also preserves the order for list in which they were processed earlier

sorted_list = [[9], [8], [1, 9, 12], [1, 2, 3, 4], [7, 8, 9, 10], [4, 5, 6, 7], [7, 8, 9, 10, 12, 16], [6, 7, 8, 9, 10, 11]]

Not able to identify the correct way to find the kth largest element from here,

returning sorted_list[-K] will not work in most of the cases where the last two sublists are of same length.

Don't confuse lists elements with sorting, sorting is done on the basis of the length of sub-lists and order is preserved in sorted_list

CodePudding user response：

You could use a dictionary to find the unique elements by length and then sort the values to find the corresponding kth element:

lst = [[1, 2, 3, 4], [1, 9, 12], [9], [8], [7, 8, 9, 10, 12, 16], [7, 8, 9, 10], [4, 5, 6, 7], [6, 7, 8, 9, 10, 11]]

# the dictionary will store the last appearing element of the corresponding key (the later one in the processing)
lookup = {len(e): e for e in lst}

# sort the values of the lookup dictionary, reverse by len
res = sorted(lookup.values(), key=len, reverse=True)

k = 2
print(res[k - 1])

k = 1
print(res[k - 1])

Output

[4, 5, 6, 7]
[6, 7, 8, 9, 10, 11]

CodePudding user response：

You can do this with Python's itertools.groupby applied to your sorted list: then accessing index -k of the grouped list gives you all lists of the kth largest length, of which you wanted the last one:

import itertools

nums = [[1, 2, 3, 4], [1, 9, 12], [9], [8], [7, 8, 9, 10, 12, 16], [7, 8, 9, 10], [4, 5, 6, 7], [6, 7, 8, 9, 10, 11]]
sorted_list = sorted(nums, key=len)

grouped_list = [list(g) for k, g in itertools.groupby(sorted_list, len)]

def kth_largest(k: int):
    return grouped_list[-k][-1]

print(kth_largest(k=2))
print(kth_largest(k=1))

gives:

[4, 5, 6, 7]
[6, 7, 8, 9, 10, 11]