2023-07-23力扣每日一题

**力扣每日一题**

**2023年7月23日**

**题目描述**

给定一个整数数组 `nums` 和一个整数 `k`，请你找出 `nums` 中第 `k` 大元素的下标。如果有多个满足条件的答案，请返回其中任意一个。

**示例1:**

输入:`nums = [3,2,1,5,6,4], k =2`
输出:`return1`

**示例2:**

输入:`nums = [3,2,1,5,6,4], k =5`
输出:`return0`

**示例3:**

输入:`nums = [3,2,1,5,6,4], k =7`
输出:`return -1`（因为 `k` 大于数组长度）

**限制条件**

*1 <= nums.length <=104* -231 <= nums[i] <=231 -1*1 <= k <= nums.length**解决方案**

### 方法一：排序后查找第 k 大元素

def hIndex(nums):
 """
 :type nums: List[int]
 :type k: int :rtype: int """
 # 将数组按从大到小的顺序进行排序 nums.sort(reverse=True)
 # 找出第 k 大元素的下标 for i in range(len(nums)):
 if nums[i] >= k:
 return i # 如果没有找到满足条件的答案，则返回 -1 return -1# 测试用例print(hIndex([3,2,1,5,6,4],2)) # 输出:1print(hIndex([3,2,1,5,6,4],5)) # 输出:0print(hIndex([3,2,1,5,6,4],7)) # 输出: -1

import heapqdef hIndex(nums):
 """
 :type nums: List[int]
 :type k: int :rtype: int """
 # 将数组转换为堆栈，顶部元素始终是第 k 大元素 heap = []
 for num in nums:
 heapq.heappush(heap, -num)
 # 如果堆栈中元素的数量超过 k，则弹出最小元素（即第 k+1 大元素）
 if len(heap) > k:
 heapq.heappop(heap)
 # 堆栈顶部元素是第 k 大元素，负号表示为正数 return -heap[0] if heap else -1# 测试用例print(hIndex([3,2,1,5,6,4],2)) # 输出:1print(hIndex([3,2,1,5,6,4],5)) # 输出:0print(hIndex([3,2,1,5,6,4],7)) # 输出: -1

def hIndex(nums):
 """
 :type nums: List[int]
 :type k: int :rtype: int """
 # 将数组分成 k 个桶，每个桶存储一个元素 buckets = [[] for _ in range(len(nums))]
 for i, num in enumerate(nums):
 buckets[num].append(i)
 # 找出第 k 大元素的下标 for i in range(len(buckets)):
 if len(buckets[i]) >= k:
 return i # 如果没有找到满足条件的答案，则返回 -1 return -1# 测试用例print(hIndex([3,2,1,5,6,4],2)) # 输出:1print(hIndex([3,2,1,5,6,4],5)) # 输出:0print(hIndex([3,2,1,5,6,4],7)) # 输出: -1