🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 599. Minimum Index Sum of Two Lists
Сложность: easy
Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.
Общая строка - это строка, которая появляется и в list1, и в list2.
Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.
Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.
Пример:
Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".
👨💻 Алгоритм:
1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.
2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.
3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.
😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public string[] FindRestaurant(string[] list1, string[] list2) {
var map = new Dictionary();
for (int i = 0; i
• ();
}
map[i + j].Add(list1[i]);
}
}
}
int minIndexSum = int.MaxValue;
foreach (var key in map.Keys) {
minIndexSum = Math.Min(minIndexSum, key);
}
return map[minIndexSum].ToArray();
}
}
Ставь 👍 и забирай 📚 Базу знаний
