두 목록에 공통이지만 가격이 다른 항목을 계산합니다.

난이도 쉽게
자주 묻는 질문 아마존 팩트 셋 GE 헬스 케어 하니웰 TCS 테슬라
이진 검색 해시 해싱 수색조회수 26

문제 정책

두 개의 목록이 제공됩니다. 각 색인에는 항목 이름과 가격이 포함됩니다. 문제 설명은 두 목록에 공통이지만 가격이 다른 항목을 세도록 요청합니다. 이는 주어진 목록과 다른 가격에서 공통된 항목 수를 알아내는 것입니다.

List1[] = {{"egg", 60}, {"butter", 20}, {"rice", 50}, {oil", 30}}

List2[] = {{“butter", 20}, {"egg", 15},{"wheat", 40}, {"rice", 60}}
2

설명 : 계란과 쌀만이 목록에서 공통적이고 가격이 다른 두 가지 요소입니다.

두 목록에 공통이지만 가격이 다른 항목을 계산하는 알고리즘

1. Declare a map and set the value of output to 0.
2. Store the first list’s name and its price to the map.
3. Traverse the second list.
    1. Check for the second list’s element, if each element’s name of the second list has a common value in list1’s name.
    2. Check for if that particular element’s price should not be equal to the element price in list1.
        1. If true, then increase the count of output by 1.
4. Return output.

설명

두 목록에 공통이지만 가격이 다른 항목을 계산합니다.

우리는 두 목록, 각 목록에는 두 개의 열 값이 포함되며 항목 이름과 가격이 포함됩니다. 임무는 두 목록 모두에서 공통 요소를 찾고 요소와 관련하여 가격이 서로 동일하지 않아야합니다. 해싱과 추가 클래스 또는 구조를 사용하고 해싱도 효율적인 솔루션을 제공합니다.

우리는 개체 목록을 사용할 것입니다. 그것은 우리의 일을 덜어 줄 것입니다. 객체 유형 목록을 만들고 각 객체에는 두 가지 속성이 포함됩니다. 속성은 항목의 이름과 가격입니다. 두 개의 목록이있는 경우 각 인덱스에 대해 두 개의 값을 취할 수 있고 각 인덱스는 객체처럼 동작하며 해당 객체에 값을 가질 수 있습니다. 그래서 우리가하려고하는 것은 첫 번째 목록을 탐색하고 각 요소를 키로, 가격을 값으로 맵에 저장하는 것입니다. 이제 첫 번째 목록의 모든 요소가 지도.

두 번째 목록을 탐색하고 목록의 각 요소를 선택합니다. 이제지도가 있고 첫 번째 목록에 가격이 저장됩니다. 따라서 현재 요소 목록의 이름이 참이면 맵에서 사용할 수 있는지 확인하고 해당 요소와 관련된 가격이 이미 저장 한 맵의 값과 같지 않은지 확인합니다. 이러한 조건이 모두 참이면 출력 수를 1만큼 늘리면됩니다. 왜냐하면 우리는 항목의 수를 세고 그 공통 항목의 수와 가격을 계산하기 때문입니다.

두 목록에 공통이지만 가격이 다른 항목을 계산하는 코드

C ++ 코드

#include<iostream>
#include<unordered_map>

using namespace std;

struct item
{
    string name;
    int price;
};
int getItemCount(item list1[], int m,item list2[], int n)
{
    unordered_map<string, int> MAP;
    int output = 0;

    for (int i = 0; i < m; i++)
        MAP[list1[i].name] = list1[i].price;

    for (int i = 0; i < n; i++)
        if ((MAP.find(list2[i].name) != MAP.end()) &&(MAP[list2[i].name] != list2[i].price))
            output++;

    return output;
}
int main()
{
    item list1[] = {{"egg", 60}, {"butter", 20}, {"rice", 50}, {"oil", 30}};
    item list2[] = {{"butter", 20}, {"egg", 15}, {"wheat", 40}, {"rice", 60}};

    int m = sizeof(list1) / sizeof(list1[0]);
    int n = sizeof(list2) / sizeof(list2[0]);

    cout<< getItemCount(list1, m, list2, n);

    return 0;
}
2

 

자바 코드

import java.util.*;

class CountItems
{
    public static class item
    {
        String name;
        int price;
        item(String name, int price)
        {
            this.name=name;
            this.price=price;
        }
    };
    public static int getItemCount(item list1[], int m,item list2[], int n)
    {
        HashMap<String, Integer> MAP=new HashMap<>();
        int output = 0;

        for (int i = 0; i < m; i++)
        {
            MAP.put(list1[i].name, list1[i].price);

        }
        for (int i = 0; i < n; i++)
        {
            if ((MAP.containsKey(list2[i].name) && (MAP.get(list2[i].name) != list2[i].price)))
                output++;
        }
        return output;
    }
    public static void main(String [] args)
    {
        item list1[] = {new item("egg", 60), new item("butter", 20),new item("rice", 50), new item("oil", 30)};

        item list2[] = {new item("butter", 20), new item("egg", 15),new item("wheat", 40), new item("rice", 60)};
        int m = list1.length;
        int n = list2.length;
        System.out.println(getItemCount(list1, m, list2, n));

    }
}
2

복잡성 분석

시간 복잡성 가격 문제가 다른 공통 항목 계산

O (m + n) 어디에 "엠" 및 "엔" list1 및 list2의 요소 수입니다.

공간 복잡성 가격 문제가 다른 공통 항목 계산

맵에 목록 1의 요소 만 저장하므로 공간 복잡도는 list1의 크기에만 의존합니다. 따라서 공간 복잡성은 O (m) 어디에 "엠" 목록의 요소 수입니다.

Translate »