返回介绍

lcs / LCS 02. 完成一半题目 / README

发布于 2024-06-17 01:04:41 字数 3456 浏览 0 评论 0 收藏 0

LCS 02. 完成一半题目

题目描述

N 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 2*N 道题目,整型数组 questions 中每个数字对应了每道题目所涉及的知识点类型。 若每位扣友选择不同的一题,请返回被选的 N 道题目至少包含多少种知识点类型。

示例 1:

输入:questions = [2,1,6,2]

输出:1

解释:有 2 位扣友在 4 道题目中选择 2 题。 可选择完成知识点类型为 2 的题目时,此时仅一种知识点类型 因此至少包含 1 种知识点类型。

示例 2:

输入:questions = [1,5,1,3,4,5,2,5,3,3,8,6]

输出:2

解释:有 6 位扣友在 12 道题目中选择题目,需要选择 6 题。 选择完成知识点类型为 3、5 的题目,因此至少包含 2 种知识点类型。

提示:

  • questions.length == 2*n
  • 2 <= questions.length <= 10^5
  • 1 <= questions[i] <= 1000

解法

方法一:计数 + 排序

我们可以用哈希表或数组 cnt 统计每种知识点类型的题目数量,然后对 cnt 进行排序,从大到小遍历 cnt,直到遍历的题目数量之和大于等于 n 即可,此时遍历的次数即为所求。

时间复杂度 $O(n \times \log n)$,空间复杂度 $O(n)$。其中 $n$ 为 questions 的长度。

class Solution:
  def halfQuestions(self, questions: List[int]) -> int:
    cnt = Counter(questions)
    ans, n = 0, len(questions) >> 1
    for _, v in cnt.most_common():
      ans += 1
      n -= v
      if n <= 0:
        break
    return ans
class Solution {
  public int halfQuestions(int[] questions) {
    int[] cnt = new int[1010];
    for (int x : questions) {
      ++cnt[x];
    }
    Arrays.sort(cnt);
    int ans = 0;
    int n = questions.length >> 1;
    for (int i = cnt.length - 1; n > 0; --i) {
      ++ans;
      n -= cnt[i];
    }
    return ans;
  }
}
class Solution {
public:
  int halfQuestions(vector<int>& questions) {
    int cnt[1001]{};
    for (int& x : questions) {
      ++cnt[x];
    }
    sort(cnt, cnt + 1001);
    int ans = 0, n = questions.size() / 2;
    for (int i = 1000; n > 0; --i) {
      ++ans;
      n -= cnt[i];
    }
    return ans;
  }
};
func halfQuestions(questions []int) (ans int) {
  cnt := make([]int, 1010)
  for _, x := range questions {
    cnt[x]++
  }
  n := len(questions) >> 1
  sort.Ints(cnt)
  for i := len(cnt) - 1; n > 0; i-- {
    ans++
    n -= cnt[i]
  }
  return
}
function halfQuestions(questions: number[]): number {
  const cnt = new Array(1010).fill(0);
  for (const x of questions) {
    ++cnt[x];
  }
  cnt.sort((a, b) => b - a);
  let ans = 0;
  let n = questions.length >> 1;
  for (let i = 0; n > 0; ++i) {
    ++ans;
    n -= cnt[i];
  }
  return ans;
}
/**
 * @param {number[]} questions
 * @return {number}
 */
var halfQuestions = function (questions) {
  const cnt = new Array(1010).fill(0);
  for (const x of questions) {
    ++cnt[x];
  }
  cnt.sort((a, b) => b - a);
  let ans = 0;
  let n = questions.length >> 1;
  for (let i = 0; n > 0; ++i) {
    ++ans;
    n -= cnt[i];
  }
  return ans;
};

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文