如何使用索引从数组中获得一个数字,该数组不按顺序排序,而数组中n是等于2或大于1的任何数字?
例如:a = [3, 4, 8, 6, 3, 5]
如果n = 3
是,那么输出将是5
。
因为[3,3,4,5,6,8]是按顺序排列的数组,而5的索引是3 + 1(因为n总是大于1)。然而,你根本不允许对数组进行排序。我该如何编写一个方法,使我能够在只使用内置方法而不使用排序的情况下做到这一点?
您可以尝试使用QuickSelect算法。它帮助你找到n个元素的无序数组的第k个最小元素这就是你正在做的。它不使用快速排序对整个数组进行排序,而是停在枢轴本身是第k个最小元素的地方。下面是该算法的伪代码链接:
https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/
希望有帮助。