Примерен уникалните елементи на масив
Н Адачи - трябва да е от неподредена масив изберете всички уникални елементи. Усложни задачата, както следва: - Опитайте се да не се използва повече памет и уникални елементи, за да пуснат в този масив.
Най-простият алгоритъм: да вземе стоката и да я сравни с всички. За работа, ние се нуждаем две гишета, първо заобикаля от всички елементи, с цел, а вторият минава всички елементи и ги сравнява с ток.
Веднага се отбележи, че променливите са винаги не са отрицателни. Това ще доведе до някои функции.
Сега, ако ние променяме масива и оставете в него само различни елементи, тя ще се промени размера си (размера имаме предвид броя на различните елементи, действителният размер ние няма да се промени), така че първоначалния размер на масива е приет от показалеца. Същата показалеца ще се съхранява броя на елементите след преобразуване.
Същността на алгоритъма е: ние приемаме елемент и да видим дали същите елементи към него. Ако не, ние копирате елемента, ако е така, се пристъпи към следващата точка. За да копирате, да се въведе контра поз - брой намерени на различни елементи на масива.
и уникален флаг, сигнализирайки, че сегашната елемент не съвпада с някой от тях вече присъства в масива.
Самостоятелно цикъл на изпитване
Цикълът на сложността на цикъл е на наш ред 2. Този алгоритъм запазва реда на елементи. За малки масиви, този алгоритъм ще бъде по-бързо от другите, заради простотата.
Там са по-бързи алгоритми. Ако се сортират масив, има елементи на едно и също един до друг. Можете да вземете една променлива предишна, който съхранява предишната стойност на елемента на масив. Ако текущият елемент е предишна, а след това го пропуснете, но ако не е, след това да копирате и промените стойността на стойността на предишна на текущия елемент.
Тъй като ние ще се използва стандартен бързо сортиране, ние също се нуждаем от размера на един елемент и елементи сравнение функция.
Алгоритъм прекарва средно на п ∙ дневник (п) + сортиране на едно преминаване през масив (по-N), т.е. сложност за п + п ∙ дневник (п). Въпреки това, ние трябва да помним, че бързасортировка за малки масиви е неефективна, така че за малки масиви, този алгоритъм е по-бавен, отколкото квадратно.
Методи на базата на броене
А ко кардиналността на елементите е малък (няколко различни елементи), можем да се преброят на събития. Това е особено полезно, когато предварително известни всички възможни елементи. Например, за да намерите всички различни буквите в думата. Тъй като броят на различни символи (в нашия случай) не е повече от 256, че е възможно да се създаде масив от 256 елемента, равна на нула.
Използвайте цифровата характер код като елемент от масив и увеличаване на стойността на съответния елемент.
Когато са известни множество елементи, обикновено се използва специализиран структура от данни, която позволява бързо да добавят елементи и се проверява за наличието, например речник. хеширан хеширан масив или асоциативен масив.
RU-Cyrl 18- Упътване Sypachev S.S. 1989-04-14 [email protected] Степан Sypachev студенти
Свързани статии