查找每个雇员下的雇员人数


难度级别 易得奖学金
经常问 ol石 GE医疗集团 微软 Myntra 高通公司 新思 Teradata数据
哈希

HashMap是最有用的数据结构之一。 查找每个雇员下的雇员人数是一个使我想起那部著名电影的开始的问题。 就像在梦中做梦。 在这里,我们有一名雇员在一名雇员下工作,依此类推。

问题陈述

那么,我们要如何解决这个问题?

出色地。 有人给美国分配了这项繁琐的工作,计算一个员工在其下工作的人数。

首先,让我们用一个测试案例来介绍问题的呈现方式:

我们给了字符对,第一个是雇员,第二个是经理。 我们要找到分配给其他人的雇员数量。

查找每个雇员下的雇员人数
显示测试用例

方法与意识形态

有很多方法可以解决问题。 但是,大多数方法要么时间太长,要么空间太长。 我在这里提到的那一种似乎是最好的解决方法。

  • 首先,在完成数据结构的最终确定时,我意识到Hashmaps是解决此问题的最佳方法
  • 其次,我意识到是否可以有效地利用它。 一个循环就足够了。
  • 我们正在维护一个哈希图。
  • 哈希图的关键是员工
  • 哈希图的值是其下的员工数
  • 我们正在运行一个循环。
  • 我们每次都会查看是否有经理的钥匙
  • 如果这样做,则将1加上前一个值
  • 我们每次都会查看是否已有员工钥匙
  • 如果这样做的话,我们在他之下工作的人们就会进入我们的网络

查找每个雇员下的雇员人数的Java代码

void group(lisa[][],int x,int y)
{
    unordered_map<char,int>store;
    for(int i=0;i<x;i++)
    {
    if(store.find(lisa[i][1])!=lisa.end())
    {
        if(store.find(lisa[i][0])!=lisa.end())
            store[lisa[i][1]]=lisa[[i][0]]+store[lisa[i][1]]+1;
        else
            store[lisa[i][1]]=store[lisa[i][1]]+1;
        else
            store.put[lisa[i][1]]=1;
    }
    for (int data : store)  
    {
        cout<<"Key = " + datagetKey() + ", Value = "+entry.getValue());
    }
}
int main() 
{
     Character[6][2]lisa;
        lisa[0][0]='A';
        lisa[0][1]='C';            
        lisa[1][0]='B';
        lisa[1][1]='C';
        lisa[2][0]='C';
        lisa[2][1]='F';
        lisa[3][0]='D';
        lisa[3][1]='E';
        lisa[4][0]='E';
        lisa[4][1]='F';
        lisa[5][0]='F';
        lisa[5][1]='F';
        group(lisa,6,2);
}

可以看出,当我们从Java转到C ++时,我们是如何从HashMap过渡到unordered_map的。

查找每个雇员下的雇员人数的C ++代码

#include<bits/stdc++.h>
using namespace std;
void group(char lisa[][2],int x)
{
    unordered_map<char,int>store;
    for(int i=0;i<x;i++)
    {
        int a=lisa[i][1];
        int b=lisa[i][0];
    if(store.find(lisa[i][1])!=store.end())
    {
        if(store.find(lisa[i][0])!=store.end())
            store[a]=store[b]+store[a]+1;
        else
            store[a]=store[a]+1;
    }
        else
            store[a]=1;
    }
    for (auto data : store)  
    {
        cout<<"Key = "<<data.first<< ", Value = "<<data.second<<endl;        
    }
}
int main() 
{
    char lisa[6][2];
        lisa[0][0]='A';
        lisa[0][1]='C';            
        lisa[1][0]='B';
        lisa[1][1]='C';
        lisa[2][0]='C';
        lisa[2][1]='F';
        lisa[3][0]='D';
        lisa[3][1]='E';
        lisa[4][0]='E';
        lisa[4][1]='F';
        lisa[5][0]='F';
        lisa[5][1]='F';
        group(lisa,6);
}
[[A,C],[B,C],[C,F],[D,E],[E,F],[F,F]]
{{A:0},{B,0},{C,2},{D,0},{E,1},{F,5}}

复杂度分析

时间复杂度= O(N)

当我们运行一个循环遍历所有元素时

空间复杂度= O(N)

当我们使用HashMap来存储所有键值对时

一个小的调整

现在,我们不仅拥有根据员工数据提供的员工信息,而且还为每位员工提供了重要性。 我们面临着一项艰巨的任务,即在每位经理的领导下报告重要性的总数。

让我们在执行BFS来仔细研究合格数据的过程中一个接一个地进行处理

  • 首先,我们将元素放入 队列。
  • 我们将继续研究下一个可能性,直到此队列变空
  • 其次,我们从队列中获得最顶层的元素
  • 我们得到员工承担的员工名单
  • 我们将所有这些员工代码放入堆栈中
  • 同时,我们正在增加我们遇到的重要性
  • 因此,在队列变空之前,我们将准备好所有重要事项

查找每个雇员下的雇员人数的Java代码

class Solution 
{
    public int getImportance(List<Employee> employees, int id) 
    {
        int sum=0;
        Queue<Integer>trav=new LinkedList<>();
        trav.add(id);
        while(!trav.isEmpty())
        {
            int cur=trav.remove();
            for(int i=0;i<employees.size();i++)
            {
                if(employees.get(i).id==cur)
                {
                    sum=sum+employees.get(i).importance;
                    List<Integer>nxt=employees.get(i).subordinates;
                    for(int j=0;j<nxt.size();j++)
                        trav.add(nxt.get(j));
                    break;
                }
            }
        }
        return sum;
    }
}

查找每个雇员下的雇员人数的C ++代码

class Solution 
{
public:
    int getImportance(vector<Employee*> employees, int id) 
    {
        int sum=0;
        queue<int>trav;
        trav.push(id);
        while(!trav.empty())
        {
            int cur=trav.front();
            trav.pop();
            for(int i=0;i<employees.size();i++)
            {
                if(employees[i]->id==cur)
                {
                    sum=sum+employees[i]->importance;
                    vector<int>nxt=employees[i]->subordinates;
                    for(int j=0;j<nxt.size();j++)
                        trav.push(nxt[j]);
                    break;
                }
            }
        }
        return sum;    
    }
};
[[1,5,[2,3]],[2,3,[]],[3,3,[]]] 1
11

复杂度分析

时间复杂度= O(V + E)

空间复杂度= O(n)

V =顶点数

E =边数

  • 首先,我们清空了运行了V次的队列。 在循环
    • 我们正在从queue = O(1)操作中删除数据
    • 遍历所有相邻边以获得克隆= O(Adj)
    • 添加邻居= O(1)操作
  • 最后,求和复杂度= V *(O(1)+ O(Adj)+ O(1))
  • 归结为O(V)+ O(V * Adj)
  • 使时间复杂度= O(V + E)
  • 空间复杂度为O(n),因为我们需要的只是一个队列

參考資料