Оптимальная цена товаров после скидок

Вход состоит из 2 списков

Продукты: [[20, ‘discount1’, ‘discount2’]] [15, ‘discount2’], [10, ‘NONE’, ‘discount1’]]

Скидки: [[‘discount1’, 1, 30], [‘discount2’, 2, 5.5]]

= = =

Каждый список продуктов состоит из [product-price, discount-name, discount-name, ….]

Каждый список скидок состоит из [discount-name, discount-type, discount-amount]

= = = =

Тип скидки 1: возьмите сумму скидки в процентах и ​​вычтите ее из цены продукта.

Тип скидки 2: возьмите сумму скидки как цену скидки и вычтите ее из цены продукта.

= = =

Цель состоит в том, чтобы определить оптимальную цену для каждого продукта и сложить ее в общую цену. После расчета каждой оптимальной цены я округляю ее до ближайшего целого числа.

Пример: (с использованием двух приведенных выше списков)

Возьмем продукт 1, который стоит 20 долларов. Примените «Discount1». ‘Discount1’ — это тип 1, поэтому сделайте следующее: 20-20 (.30) = 14 -> Math.round (14) = 14

Теперь примените «Discount2». ‘Discount2’ — это тип 2, поэтому сделайте следующее: 20 — 5.5 = 14.5 -> Math.round (14.5) = 15

Поскольку 14 <15, я беру 14 как оптимальную цену для продукта 1 и добавляю ее к переменной finalPrice. Я делаю это для остальных продуктов

public class Solution {
        static class DisHelper {
        int type;
        double d;
        DisHelper(int type, double d) {
            this.type=type;
            this.d=d;
        }
    }
    public static int Price(List<List<String>> products, List<List<String>> discounts) {
        int finalPrice=0;
        
        HashMap<String, DisHelper> map = new HashMap<>();
        for(List<String> list: discounts) {
            map.put(list.get(0), new DisHelper(Integer.parseInt(list.get(1)), Double.parseDouble(list.get(2))));
        }
        
        for(List<String> list: products) {
            double originalPrice = Double.parseDouble(list.get(0));
            double optimalPrice = originalPrice;
            for(int i=1;i<list.size();i++) {
                if(list.get(i).equals("NONE")) {
                    continue;
                }
                double price1=originalPrice;
                DisHelper subDisObj = map.get(list.get(i));
                if(subDisObj.type==1) {
                    price1=Math.round(price1-(price1*(subDisObj.d/(double)100)));
                } else if(subDisObj.type==2) {
                    price1=Math.round(price1-subDisObj.d);
                }
                optimalPrice=Math.min(optimalPrice, price1);

            }

            finalPrice+=(int)optimalPrice;
        }
        return finalPrice;
    }

    public static void main(String[] args) {

        List<List<String>> products = new ArrayList<>();
        List<List<String>> discounts = new ArrayList<>();
        products.add(new ArrayList<>(List.of("20", "discount1", "discount2")));
        products.add(new ArrayList<>(List.of("15", "discount2")));
        products.add(new ArrayList<>(List.of("10", "NONE", "discount1")));
        discounts.add(new ArrayList<>(List.of("discount1", "1", "30")));
        discounts.add(new ArrayList<>(List.of("discount2", "2", "5.5")));
        System.out.println(Price(products, discounts));

    }
}

Анализ
Допустим, у нас есть M товаров, N скидок и k наименований скидок для каждого продукта.

Заполнение HashMap: O (N)

Просмотр каждого продукта: O (M)

Прохождение каждой скидки (для каждого продукта) O (M * k)

Временная сложность: O (max (N, M * k))

Сложность пространства: O (N) для Hashmap.

Правильны ли временные и пространственные сложности?

Могу ли я оптимизировать этот код?

Ваши временные и пространственные сложности верны. Вы также можете записать свою временную сложность как O (N + M * k), что эквивалентно.

Есть несколько вещей, которые можно улучшить в вашем коде, но это не должно сильно менять его рабочие характеристики.

Соглашения об именах

Большинство ваших переменных названы неправильно или имеют не совсем полезные имена, как и DisHelper. Я предполагаю, что вы выполняете онлайн-вызов, в котором Price — это навязанная подпись, поэтому я проигнорирую его.

Вызов DisHelper так вместо DiscountHelper, вы сэкономите 4 символа в обмен на ясность кода.

Ваш finalPrice действительно больше totalPrice, поскольку это сумма всех ваших оптимальных цен. На первый взгляд, я ожидал, что с таким названием будет указана окончательная цена текущего продукта.

Это два примера, но price1, subDisObj а также list поделитесь схожими проблемами.

Кодирование против интерфейса

Вы должны (почти) никогда явно не объявлять переменную как HashMap. Поскольку вы используете только Map интерфейс, вместо этого вы должны сделать Map<String, DisHelper> map = new HashMap<>();. Таким образом, изменив HashMap к любому другому типу Map будет меньше влиять на ваш код.

Обработка номеров

Кажется, что ваша исходная цена всегда будет int но вы разбираете это как double. Затем вы отбрасываете его обратно в int в последний момент при добавлении в finalPrice.

Вместо этого вы могли сохранить его только как int, и преобразовать результат скидки как int. Вы можете сэкономить бесконечно малое количество времени, сравнивая два int (32 бита) вместо двух double (64 бит). С очень большим количеством тестовых примеров в онлайн-задаче это потенциально может сэкономить вам несколько миллисекунд, но, вероятно, не намного больше.

Один из способов сделать это — заменить

                double price1=originalPrice;
                DisHelper subDisObj = map.get(list.get(i));
                if(subDisObj.type==1) {
                    price1=Math.round(price1-(price1*(subDisObj.d/(double)100)));
                } else if(subDisObj.type==2) {
                    price1=Math.round(price1-subDisObj.d);
                }
                optimalPrice=Math.min(optimalPrice, price1);

к

                int currentPrice;
                DisHelper subDisObj = map.get(list.get(i));
                if (subDisObj.type==1) {
                    currentPrice = (int) Math.round(originalPrice*(1-subDisObj.d/100.0));
                } else if (subDisObj.type==2) {
                    currentPrice = (int) Math.round(originalPrice-subDisObj.d);
                }
                optimalPrice=Math.min(optimalPrice, currentPrice);