LeetCode 1341. 电影评分

Categories:

题目描述
思路分析
1. 解法一：统计 + 排序（推荐）
相似题目

题目描述

✅ 1341. 电影评分

思路分析

解法一：统计 + 排序（推荐）

核心思路：

统计每个用户的评分次数，取次数最多且姓名字典序最小的用户。

过滤 2020 年 2 月的评分记录，统计每部电影平均评分。

取平均评分最高且电影名最小的电影。

复杂度分析：

时间复杂度：O(n + m)，其中 n 为评分记录数，m 为电影/用户数。

空间复杂度：O(n)。

import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public String[] movieRating(List<User> users, List<Movie> movies, List<MovieRating> ratings) {
        Map<Integer, String> userName = new HashMap<>();
        for (User u : users) {
            userName.put(u.userId, u.name);
        }
        Map<Integer, String> movieTitle = new HashMap<>();
        for (Movie m : movies) {
            movieTitle.put(m.movieId, m.title);
        }

        Map<Integer, Integer> userCnt = new HashMap<>();
        for (MovieRating r : ratings) {
            userCnt.put(r.userId, userCnt.getOrDefault(r.userId, 0) + 1);
        }
        String bestUser = "";
        int bestCnt = -1;
        for (Map.Entry<Integer, Integer> e : userCnt.entrySet()) {
            String name = userName.get(e.getKey());
            int cnt = e.getValue();
            if (cnt > bestCnt || (cnt == bestCnt && name.compareTo(bestUser) < 0)) {
                bestCnt = cnt;
                bestUser = name;
            }
        }

        Map<Integer, int[]> sumCnt = new HashMap<>();
        for (MovieRating r : ratings) {
            if (r.createdAt.compareTo("2020-02-01") < 0 || r.createdAt.compareTo("2020-02-29") > 0) {
                continue;
            }
            int[] sc = sumCnt.computeIfAbsent(r.movieId, k -> new int[2]);
            sc[0] += r.rating;
            sc[1] += 1;
        }

        String bestMovie = "";
        double bestAvg = -1.0;
        for (Map.Entry<Integer, int[]> e : sumCnt.entrySet()) {
            int[] sc = e.getValue();
            double avg = (double) sc[0] / sc[1];
            String title = movieTitle.get(e.getKey());
            if (avg > bestAvg || (Math.abs(avg - bestAvg) < 1e-12 && title.compareTo(bestMovie) < 0)) {
                bestAvg = avg;
                bestMovie = title;
            }
        }

        return new String[] {bestUser, bestMovie};
    }

    static class User {
        int userId;
        String name;
        User(int userId, String name) {
            this.userId = userId;
            this.name = name;
        }
    }

    static class Movie {
        int movieId;
        String title;
        Movie(int movieId, String title) {
            this.movieId = movieId;
            this.title = title;
        }
    }

    static class MovieRating {
        int userId;
        int movieId;
        int rating;
        String createdAt;
        MovieRating(int userId, int movieId, int rating, String createdAt) {
            this.userId = userId;
            this.movieId = movieId;
            this.rating = rating;
            this.createdAt = createdAt;
        }
    }
}

type User struct {
    UserId int
    Name   string
}

type Movie struct {
    MovieId int
    Title   string
}

type MovieRating struct {
    UserId    int
    MovieId   int
    Rating    int
    CreatedAt string
}

func movieRating(users []User, movies []Movie, ratings []MovieRating) []string {
    userName := make(map[int]string)
    for _, u := range users {
        userName[u.UserId] = u.Name
    }
    movieTitle := make(map[int]string)
    for _, m := range movies {
        movieTitle[m.MovieId] = m.Title
    }

    userCnt := make(map[int]int)
    for _, r := range ratings {
        userCnt[r.UserId]++
    }

    bestUser := ""
    bestCnt := -1
    for id, cnt := range userCnt {
        name := userName[id]
        if cnt > bestCnt || (cnt == bestCnt && (bestUser == "" || name < bestUser)) {
            bestCnt = cnt
            bestUser = name
        }
    }

    sumCnt := make(map[int][2]int)
    for _, r := range ratings {
        if r.CreatedAt < "2020-02-01" || r.CreatedAt > "2020-02-29" {
            continue
        }
        sc := sumCnt[r.MovieId]
        sc[0] += r.Rating
        sc[1] += 1
        sumCnt[r.MovieId] = sc
    }

    bestMovie := ""
    bestAvg := -1.0
    for id, sc := range sumCnt {
        avg := float64(sc[0]) / float64(sc[1])
        title := movieTitle[id]
        if avg > bestAvg || (absFloat(avg-bestAvg) < 1e-12 && (bestMovie == "" || title < bestMovie)) {
            bestAvg = avg
            bestMovie = title
        }
    }

    return []string{bestUser, bestMovie}
}

func absFloat(x float64) float64 {
    if x < 0 {
        return -x
    }
    return x
}

相似题目

题目	难度	考察点
1107. 每日新用户统计	中等	统计
1158. 市场分析 I	中等	分组统计
1193. 每月交易 I	中等	分组统计
1327. 列出指定时间段内所有的下单产品	简单	统计
1179. 重新格式化部门表	简单	分组统计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/91268711