Мой вопрос связан с этим ранним вопросом
В одном из моих интервью мне было предложено написать функцию, чтобы определить первый уникальный символ в строке во времени O (n), используя в качестве дополнительного пространства только булевский массив длины n. То есть, найдите первую не повторяющуюся букву в строке, используя только сложность O (n) и массив bool длины n. Может ли кто-нибудь предложить, как его решить с помощью массива bool?
Ну, если размер набора символов является постоянным... Скажем, например, 0-255...
Сканировать строку, ищущую символ 0.
Затем сканируйте строку, которая ищет символ 1.
Затем сканируйте строку, которая ищет символ 2.
...
Наконец, сканируйте строку, которая ищет символ 255.
Это занимает 256 * n операций, которые являются O (n).
Во время каждого сканирования, если символ уникален, отметьте его положение в растровом изображении. В конце верните символ в первую отмеченную позицию. (Или просто записать первый уникальный символ и его местоположение с помощью бит k + log (n). Используйте жестко закодированную таблицу поиска или что угодно для очень маленького n, в противном случае n бит великодушны.)
Хотя почему-то я подозреваю, что это не то, что имел в виду интервьюер.
private static void FirstNonRepeatingCharacters()
{
string s = "abbazccdde";
var result = from item in s
group item by item into groupedItems
where groupedItems.Count() == 1
select groupedItems.Key;
Console.WriteLine(result.First());
}
Реализация С#
Для решения с одним проходом
Поддерживать 2 структуры данных:
LinkedHashMap имеет
O (1) поиск
class Node
{
char data;
Node next;
Node prev;
};
class LinkedHashMap
{
// This will keep the insertion order intact
Node listHead;
Node currentTail = listHead;
HashTable<char, Node> charExistsMap;
void Add(char ch)
{
if(!charExistsMap.ContainsKey(ch))
{
// Add to both hashtable and linkedlist
Node n = new Node(ch);
n->next = null;
n->prev = curentTail; // Added To List
currentTail = n;
charExistMap.Add(ch, n);
}
else
{
// Remove from both hashtable and linkedlist
Node n = charExistMap.Remove(ch);
if(n->prev != null)
{
n->prev->next = n->next
listHead = n->next; // update head
}
if(n->next != null)
n->next->prev = n->prev;
}
}
char GetFirstNonRepeatingChar()
{
return listHead->data;
}
}
После прохождения исходной строки глава LinkedHashMap будет содержать первый символ, который не повторяется.
public class FirstUniqueChar {
public static void main(String[] args) {
String test = "ABxacd";
test = test.toUpperCase();
for (int i = 0; i < test.length(); i++) {
int firstIndex = test.indexOf(test.charAt(i));
int lastIndex = test.lastIndexOf(test.charAt(i));
if (firstIndex == lastIndex) {
System.out.println("First unique char of String " + test.charAt(i));
break;
}
}
}
}
Сделайте это за два прохода:
1-й проход: создайте массив bool размером 256 и для каждого char в текстовой пометке элемент index int (который char). Это берет O (n).
2-й проход: для каждого char в тексте проверьте, отмечен ли соответствующий элемент массива. Если нет, тогда вы нашли свой ответ. Это также принимает O (n).
Имейте два булевых массива, увиденных и увиденных. Цикл по строке заполняет массивы. Перебирайте строку, снова проверяя, присутствует ли символ вначале, но не отображается много. Если это ваш первый неповторяющийся символ.
Вот пример кода в python.
subject = "ttojxxlma"
seenOnce = [False for i in range(256)]
seenMany = [False for i in range(256)]
for c in subject:
index = ord(c)
if seenOnce[index] == False:
seenOnce[index] = True
else:
seenMany[index] = True
for c in subject:
index = ord(c)
if seenOnce[index]==True and seenMany[index] != True:
print(c)
break
Хорошо, что все еще использует слишком логический массив (или списки python = P). Чтобы использовать только один массив, у вас может быть один массив, который удваивает количество символов. Вместо доступа к второму массиву удвоить индекс и получить доступ к большому. Но это просто грязно.
Не уверен, что это можно сделать с меньшим объемом.