讨论/技术交流/分享|美团面试题目/
分享|美团面试题目

求给定数组滑动窗口的众数
输入n和k,n表示数组长度,k表示窗口宽度,输出每个窗口的众数,众数定义:窗口内出现次数最多的数,如果有多个,输出数值最小的如[1,2,2] -> 2 ,[1,1,3,3,2,2] -> 1。
示例:
输入:
n = 5, k = 3
[1,2,2,1,3]
输出:
[2,2,1]
有没有大佬给个思路?

1
共 12 个回复
package java_02meituan;

import java.util.*;

java版本 测试用例输出[2 2 1];
/**
 * @author Panda
 * @create 2021-25-9:46
 */
public class Main5 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =0,k=0;
        if(sc.hasNextInt()){
            n = sc.nextInt();
            k = sc.nextInt();
        }
        int[] arr = new int[n];

        for(int i = 0;i<n;i++){
            if(sc.hasNextInt()){
                arr[i] = sc.nextInt();
            }
        }
        List<Integer> list = new LinkedList<>();
        for(int j = 0; j < n-k+1;j++){
            list.add(searchMode(arr,j,j+k-1)) ;
        }
        System.out.println(list.toString());


    }
    public static Integer searchMode(int[] arr,int l,int r){
        HashMap<Integer,Integer> map = new HashMap<>();
        TreeMap<Integer,Integer> sortmap = new TreeMap<>();

        for(int i = l; i <= r; i++){
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }
        for(int i = l; i <= r; i++){
            //需要判断存不存在
            int temp = map.get(arr[i]);//这是频次,应该比较值
            if(sortmap.containsKey(temp)){
                if(arr[i]<sortmap.get(temp)){
                    sortmap.put(temp,arr[i]);
                }
            }else{
                sortmap.put(temp,arr[i]);
            }
        }
        Integer res = sortmap.lastKey();
        Integer out = sortmap.get(res);
        return out;

    }
}

1

这个时间复杂度是N²logK

1

c++实现的话用一个map和一个mutimap。

js:


 function getNumber(arr){
        const obj ={};
        let maxValue =0;
        let maxKey =0;
        arr.forEach((item) => {
            if (obj[item]){
                obj[item] +=1;
            } else {
                obj[item] = 1;
            }
        })
        for(let i in obj){
            if (obj[i] > maxValue){
                maxValue = obj[i];
                maxKey = i;
            }
        }
        return maxKey;
    }

昨天AC了,复杂度NlogN

用的两个map

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>


using namespace std;

typedef long long ll;

int arr[100005];
map<int, int> mapp;

struct cmp {

    bool operator()(int i, int j) const {
        if (mapp[i] == mapp[j])return i < j;
        return mapp[i] > mapp[j];
    }

};

int main() {

    int n, k;
    cin >> n >> k;

    set<int, cmp> ans;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for (int i = 0; i < k; i++) {
        mapp[arr[i]]++;
    }
    for (auto &a:mapp) {
        ans.insert(a.first);
    }
    cout << *ans.begin() << endl;
    for (int i = k; i < n; i++) {
        ans.erase(arr[i - k]);
        ans.erase(arr[i]);
        mapp[arr[i - k]]--;
        mapp[arr[i]]++;
        if (mapp[arr[i - k]])ans.insert(arr[i - k]);
        ans.insert(arr[i]);
        cout << *ans.begin() << endl;
    }

    return 0;
}

单调队列可行吗

我也不会,暴力过了70%多,后面超时,mark一下,看有没有完美解法

这题我AC了。思路:使用HashMap维护数字及其出现的频数,使用TreeSet重写比较方法来维护题目要求的顺序,即频数高的在前,频数低的靠后;频数相同时,看数字哪个更小。然后就是滑窗的框架了。

可以用优先队列来实现一个topK问题,不过需要排序的是key出现的频数。