Рубрики

Удалить дубликаты из заданной строки

Для данной строки S задача состоит в том, чтобы удалить все дубликаты в данной строке.

Ниже приведены различные способы удаления дубликатов в строке.

МЕТОД 1 (простой)

C ++

// Программа CPP для удаления дублирующего символа
// из массива символов и распечатать в отсортированном виде
// заказ
#include <bits/stdc++.h>

using namespace std;

  

char *removeDuplicate(char str[], int n)

{

   // Используется как индекс в измененной строке

   int index = 0;   

     

   // Обход всех персонажей

   for (int i=0; i<n; i++) {

         

     // Проверяем, присутствует ли str [i] перед ним

     int j;  

     for (j=0; j<i; j++) 

        if (str[i] == str[j])

           break;

       

     // Если нет, то добавьте его в

     // результат.

     if (j == i)

        str[index++] = str[i];

   }

     

   return str;

}

  
// Код драйвера

int main()

{

   char str[]= "geeksforgeeks";

   int n = sizeof(str) / sizeof(str[0]);

   cout << removeDuplicate(str, n);

   return 0;

}

Джава

// Java-программа для удаления повторяющихся символов
// из массива символов и распечатать в отсортированном виде
// заказ

import java.util.*;

  

class GFG 

{

    static String removeDuplicate(char str[], int n)

    {

        // Используется как индекс в измененной строке

        int index = 0;

  

        // Обход всех персонажей

        for (int i = 0; i < n; i++)

        {

  

            // Проверяем, присутствует ли str [i] перед ним

            int j;

            for (j = 0; j < i; j++) 

            {

                if (str[i] == str[j])

                {

                    break;

                }

            }

  

            // Если нет, то добавьте его в

            // результат.

            if (j == i) 

            {

                str[index++] = str[i];

            }

        }

        return String.valueOf(Arrays.copyOf(str, index));

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        char str[] = "geeksforgeeks".toCharArray();

        int n = str.length;

        System.out.println(removeDuplicate(str, n));

    }

}

  
// Этот код предоставлен Rajput-Ji

python3

# Python3 программа для удаления повторяющихся символов
# из массива символов и принтера отсортированы
# заказ

def removeDuplicate(str, n):

      

    # Используется как индекс в измененной строке

    index = 0

      

    # Пройдите через всех персонажей

    for i in range(0, n):

          

        # Проверьте, присутствует ли str [i] перед ним

        for j in range(0, i + 1):

            if (str[i] == str[j]):

                break

                  

        # Если его нет, добавьте его в

        # результат.

        if (j == i):

            str[index] = str[i]

            index += 1

              

    return "".join(str[:index])

  
# Код драйвера

str= "geeksforgeeks"

n = len(str)

print(removeDuplicate(list(str), n))

  
# Этот код предоставлен SHUBHAMSINGH10

C #

// C # программа для удаления дублирующего символа
// из массива символов и распечатать в отсортированном виде
// заказ

using System;

using System.Collections.Generic;

class GFG 

{

static String removeDuplicate(char []str, int n)

{

    // Используется как индекс в измененной строке

    int index = 0;

  

    // Обход всех персонажей

    for (int i = 0; i < n; i++)

    {

  

        // Проверяем, присутствует ли str [i] перед ним

        int j;

        for (j = 0; j < i; j++) 

        {

            if (str[i] == str[j])

            {

                break;

            }

        }

  

        // Если нет, то добавьте его в

        // результат.

        if (j == i) 

        {

            str[index++] = str[i];

        }

    }

    char [] ans = new char[index];

    Array.Copy(str, ans, index);

    return String.Join("", ans);

}

  
// Код драйвера

public static void Main(String[] args)

{

    char []str = "geeksforgeeks".ToCharArray();

    int n = str.Length;

    Console.WriteLine(removeDuplicate(str, n));

}
}

  
// Этот код предоставлен PrinciRaj1992

Выход:

geksfor

Сложность времени: O (n * n)
Вспомогательное пространство: O (1)
Сохраняет порядок элементов таким же, как и для ввода.

МЕТОД 2 (Используйте BST)
используйте набор в c ++ stl, который реализует самобалансирующееся двоичное дерево поиска.

// Программа CPP для удаления дублирующего символа
// из массива символов и распечатать в отсортированном виде
// заказ
#include <bits/stdc++.h>

using namespace std;

  

char *removeDuplicate(char str[], int n)

{

    // создать набор, используя строковые символы

    // исключая '/ 0'

    set<char>s (str, str+n-1);

  

    // выводим содержимое набора

    int i = 0;

    for (auto x : s)

       str[i++] = x;

    str[i] = '\0';

  

    return str;

}

  
// Код драйвера

int main()

{

   char str[]= "geeksforgeeks";

   int n = sizeof(str) / sizeof(str[0]);

   cout << removeDuplicate(str, n);

   return 0;

}

Выход:

  efgkors

Сложность времени : O (n Log n)
Вспомогательное пространство : O (n)

Спасибо Anivesh Tiwari за предложенный подход.

Не сохраняет порядок элементов так же, как ввод, но печатает их в отсортированном порядке.

МЕТОД 3 (Использовать сортировку)
Алгоритм:

  1) Sort the elements.
  2) Now in a loop, remove duplicates by comparing the 
      current character with previous character.
  3)  Remove extra characters at the end of the resultant string.


Пример:

Input string:  geeksforgeeks
1) Sort the characters
   eeeefggkkorss
2) Remove duplicates
    efgkorskkorss
3) Remove extra characters
     efgkors

Обратите внимание, что этот метод не сохраняет исходный порядок входной строки. Например, если мы хотим удалить дубликаты для geeksforgeeks и сохранить порядок символов одинаковым, тогда вывод должен быть geksfor, но функция выше возвращает efgkos. Мы можем изменить этот метод, сохранив исходный порядок. МЕТОД 2 сохраняет порядок таким же.

Реализация:

C ++

// C ++ prigram для удаления дубликатов, порядок
// символы не поддерживаются в этой программе
#include<bits/stdc++.h>

using namespace std;

  
/ * Функция удаления дубликатов в отсортированном массиве * /

char *removeDupsSorted(char *str)

{

    int res_ind = 1, ip_ind = 1;

  

    / * Вместо удаления дубликатов символов * /

    while (*(str + ip_ind))

    {

        if (*(str + ip_ind) != *(str + ip_ind - 1))

        {

            *(str + res_ind) = *(str + ip_ind);

            res_ind++;

        }

        ip_ind++;

    }

  

    / * После вышеприведенного шага строка efgkorskkorss.

       Удаление лишних ккорсс после строки * /

    *(str + res_ind) = '\0';

  

    return str;

}

  
/ * Функция удаляет повторяющиеся символы из строки

   Эта функция работает на месте и заполняет нулевые символы

   в свободном месте осталось * /

char *removeDups(char *str)

{

   int n = strlen(str);

  

   // Сортировка массива символов

   sort(str, str+n);

  

   // Удалить дубликаты из отсортированного

   return removeDupsSorted(str);

}

  
/ * Драйвер программы для проверки removeDups * /

int main()

{

  char str[] = "geeksforgeeks";

  cout << removeDups(str);

  return 0;

}

С

// C ++ программа для удаления дубликатов, порядок
// символы не поддерживаются в этой программе
# include <stdio.h>
# include <stdlib.h>

  
/ * Функция удаления дубликатов в отсортированном массиве * /

char *removeDupsSorted(char *str);

  
/ * Функция Utitlity для сортировки массива A [] * /

void quickSort(char A[], int si, int ei);

  
/ * Функция удаляет повторяющиеся символы из строки

   Эта функция работает на месте и заполняет нулевые символы

   в свободном месте осталось * /

char *removeDups(char *str)

{

  int len = strlen(str);

  quickSort(str, 0, len-1);

  return removeDupsSorted(str);

}     

  
/ * Функция удаления дубликатов в отсортированном массиве * /

char *removeDupsSorted(char *str)

{

  int res_ind = 1, ip_ind = 1;

  

  / * Вместо удаления дубликатов символов * /

  while (*(str + ip_ind))

  {

    if (*(str + ip_ind) != *(str + ip_ind - 1))

    {

      *(str + res_ind) = *(str + ip_ind);

      res_ind++;

    }

    ip_ind++;

  }      

  

  / * После вышеприведенного шага строка efgkorskkorss.

     Удаление лишних ккорсс после строки * /

  *(str + res_ind) = '\0';

  

  return str;

}

  
/ * Драйвер программы для проверки removeDups * /

int main()

{

  char str[] = "geeksforgeeks";

  printf("%s", removeDups(str));

  getchar();

  return 0;

}

  
/ * СЛЕДУЮЩИЕ ФУНКЦИИ ТОЛЬКО ДЛЯ СОРТИРОВКИ

    ЦЕЛЬ */

void exchange(char *a, char *b)

{

  char temp;

  temp = *a;

  *a   = *b;

  *b   = temp;

}

  

int partition(char A[], int si, int ei)

{

  char x = A[ei];

  int i = (si - 1);

  int j;

  

  for (j = si; j <= ei - 1; j++)

  {

    if (A[j] <= x)

    {

      i++;

      exchange(&A[i], &A[j]);

    }

  }

  exchange (&A[i + 1], &A[ei]);

  return (i + 1);

}

  
/ * Реализация быстрой сортировки
A [] -> Массив для сортировки
si -> Начальный индекс
ei -> Конечный индекс
* /

void quickSort(char A[], int si, int ei)

{

  int pi;    / * Индекс разделения * /

  if (si < ei)

  {

    pi = partition(A, si, ei);

    quickSort(A, si, pi - 1);

    quickSort(A, pi + 1, ei);

  }

}

Джава

// Java программа для удаления дубликатов, порядок
// символы не поддерживаются в этой программе

  

import java.util.Arrays;

  

public class GFG 

{

    / * Метод удаления дубликатов в отсортированном массиве * /

    static String removeDupsSorted(String str)

    {

        int res_ind = 1, ip_ind = 1;

          

        // Массив символов для удаления повторяющихся символов

        char arr[] = str.toCharArray();

          

        / * Вместо удаления дубликатов символов * /

        while (ip_ind != arr.length)

        {

            if(arr[ip_ind] != arr[ip_ind-1])

            {

                arr[res_ind] = arr[ip_ind];

                res_ind++;

            }

            ip_ind++;

            

        }

      

        str = new String(arr);

        return str.substring(0,res_ind);

    }

       

    / * Метод удаляет повторяющиеся символы из строки

       Эта функция работает на месте и заполняет нулевые символы

       в свободном месте осталось * /

    static String removeDups(String str)

    {

       // Сортировка массива символов

       char temp[] = str.toCharArray();

       Arrays.sort(temp);

       str = new String(temp);

         

       // Удалить дубликаты из отсортированного

       return removeDupsSorted(str);

    }

       

    // Метод драйвера

    public static void main(String[] args)

    {

        String str = "geeksforgeeks";

        System.out.println(removeDups(str));

    }

}

питон

# Программа Python для удаления дубликатов, порядок
# символов не поддерживается в этой программе

  
# Утилита для преобразования строки в список

def toMutable(string):

    temp = []

    for x in string:

        temp.append(x)

    return temp

  
# Утилита для преобразования строки в список

def toString(List):

    return ''.join(List)

  
# Функция удаления дубликатов в отсортированном массиве

def removeDupsSorted(List):

    res_ind = 1

    ip_ind = 1

  

    # Вместо удаления повторяющихся символов

    while ip_ind != len(List):

        if List[ip_ind] != List[ip_ind-1]:

            List[res_ind] = List[ip_ind]

            res_ind += 1

        ip_ind+=1

  

    # После вышеуказанного шага строка efgkorskkorss.

    # Удаление лишних kkorss после строки

    string = toString(List[0:res_ind])

  

    return string

  
# Функция удаляет повторяющиеся символы из строки
# Эта функция работает на месте и заполняет нулевые символы
# в свободном месте осталось

def removeDups(string):

    # Конвертировать строку в список

    List = toMutable(string)

  

    # Сортировка списка символов

    List.sort()

  

    # Удалить дубликаты из отсортированного

    return removeDupsSorted(List)

  
# Драйвер программы для проверки вышеуказанных функций

string = "geeksforgeeks"

print removeDups(string)

  
# Этот код предоставлен Bhavya Jain

C #

// C # программа для удаления дубликатов, порядок
// символы не поддерживаются в этой программе

using System;

      

class GFG 

{

    / * Метод удаления дубликатов в отсортированном массиве * /

    static String removeDupsSorted(String str)

    {

        int res_ind = 1, ip_ind = 1;

          

        // Массив символов для удаления повторяющихся символов

        char []arr = str.ToCharArray();

          

        / * Вместо удаления дубликатов символов * /

        while (ip_ind != arr.Length)

        {

            if(arr[ip_ind] != arr[ip_ind-1])

            {

                arr[res_ind] = arr[ip_ind];

                res_ind++;

            }

            ip_ind++;

              

        }

      

        str = new String(arr);

        return str.Substring(0,res_ind);

    }

      

    / * Метод удаляет повторяющиеся символы из строки

    Эта функция работает на месте и заполняет нулевые символы

    в свободном месте осталось * /

    static String removeDups(String str)

    {

    // Сортировка массива символов

    char []temp = str.ToCharArray();

    Array.Sort(temp);

    str = String.Join("",temp);

          

    // Удалить дубликаты из отсортированного

    return removeDupsSorted(str);

    }

      

    // Метод драйвера

    public static void Main(String[] args)

    {

        String str = "geeksforgeeks";

        Console.WriteLine(removeDups(str));

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

efgkors

Сложность времени: O (n log n) Если вместо быстрой сортировки мы используем алгоритм сортировки nlogn.

МЕТОД 4 (использовать хеширование)
Алгоритм:

1: Initialize:
    str  =  "test string" /* input string */
    ip_ind =  0          /* index to  keep track of location of next
                             character in input string */
    res_ind  =  0         /* index to  keep track of location of
                            next character in the resultant string */
    bin_hash[0..255] = {0,0, ….} /* Binary hash to see if character is 
                                        already processed or not */
2: Do following for each character *(str + ip_ind) in input string:
              (a) if bin_hash is not set for *(str + ip_ind) then
                   // if program sees the character *(str + ip_ind) first time
                         (i)  Set bin_hash for *(str + ip_ind)
                         (ii)  Move *(str  + ip_ind) to the resultant string.
                              This is done in-place.
                         (iii) res_ind++
              (b) ip_ind++
  /* String obtained after this step is "te sringng" */
3: Remove extra characters at the end of the resultant string.
  /*  String obtained after this step is "te sring" */

Реализация:

C ++

#include <bits/stdc++.h>

using namespace std; 

# define NO_OF_CHARS 256 
# define bool int 

  
/ * Функция удаляет повторяющиеся символы из строки
Эта функция работает на месте и заполняет нулевые символы
в свободном месте осталось * /

char *removeDups(char str[]) 

    bool bin_hash[NO_OF_CHARS] = {0}; 

    int ip_ind = 0, res_ind = 0; 

    char temp; 

      

    / * Вместо удаления дубликатов символов * /

    while (*(str + ip_ind)) 

    

        temp = *(str + ip_ind); 

        if (bin_hash[temp] == 0) 

        

            bin_hash[temp] = 1; 

            *(str + res_ind) = *(str + ip_ind); 

            res_ind++; 

        

        ip_ind++; 

    

      

    / * После вышеприведенного шага string будет stringiittg.

        Удаление лишних iittg после строки * /

    *(str+res_ind) = '\0'

      

    return str; 

  
/ * Код водителя * /

int main() 

    char str[] = "geeksforgeeks"

    cout << removeDups(str); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

# include <stdio.h>
# include <stdlib.h>
# define NO_OF_CHARS 256
# define bool int

  
/ * Функция удаляет повторяющиеся символы из строки

   Эта функция работает на месте и заполняет нулевые символы

   в свободном месте осталось * /

char *removeDups(char *str)

{

  bool bin_hash[NO_OF_CHARS] = {0};

  int ip_ind = 0, res_ind = 0;

  char temp;    

  

  / * Вместо удаления дубликатов символов * /

  while (*(str + ip_ind))

  {

    temp = *(str + ip_ind);

    if (bin_hash[temp] == 0)

    {

        bin_hash[temp] = 1;

        *(str + res_ind) = *(str + ip_ind);

        res_ind++;

    }

    ip_ind++;

  }      

  

  / * После вышеприведенного шага string будет stringiittg.

     Удаление лишних iittg после строки * /

  *(str+res_ind) = '\0';   

  

  return str;

}

  
/ * Драйвер программы для проверки removeDups * /

int main()

{

    char str[] = "geeksforgeeks";

    printf("%s", removeDups(str));

    getchar();

    return 0;

}

Джава

// Java-программа для удаления дубликатов

import java.util.*;

  

class RemoveDuplicates

{

    / * Функция удаляет повторяющиеся символы из строки

    Эта функция работает на месте * /

    void removeDuplicates(String str)

    {

        LinkedHashSet<Character> lhs = new LinkedHashSet<>();

        for(int i=0;i<str.length();i++)

            lhs.add(str.charAt(i));

          

        // выводим строку после удаления дублирующих элементов

        for(Character ch : lhs)

            System.out.print(ch);

    }

      

    / * Драйверная программа для проверки удаления дубликатов * /

    public static void main(String args[])

    {

        String str = "geeksforgeeks";

        RemoveDuplicates r = new RemoveDuplicates();

        r.removeDuplicates(str);

    }

}

  
// Этот код предоставлен Амитом Хандельвалом (Amit Khandelwal 1)

питон

# Программа Python для удаления дублирующихся символов из
# строка ввода

NO_OF_CHARS = 256

  
# Поскольку строки в Python неизменны и не могут быть изменены
# Эта служебная функция преобразует строку в список

def toMutable(string):

    List = []

    for i in string:

        List.append(i)

    return List

  
# Сервисная функция, которая изменяет список на строку

def toString(List):

    return ''.join(List)

  
# Функция удаляет повторяющиеся символы из строки
# Эта функция работает на месте и заполняет нулевые символы
# в свободном месте осталось

def removeDups(string):

    bin_hash = [0] * NO_OF_CHARS

    ip_ind = 0

    res_ind = 0

    temp = ''

    mutableString = toMutable(string)

  

    # Вместо удаления повторяющихся символов

    while ip_ind != len(mutableString):

        temp = mutableString[ip_ind]

        if bin_hash[ord(temp)] == 0:

            bin_hash[ord(temp)] = 1

            mutableString[res_ind] = mutableString[ip_ind]

            res_ind+=1

        ip_ind+=1

  

     # После вышеприведенного шага string будет stringiittg.

     # Удаление лишних iittg после строки

     return toString(mutableString[0:res_ind])

  
# Драйвер программы для проверки вышеуказанных функций

string = "geeksforgeeks"

print removeDups(string)

  
# Более короткая версия для этой программы выглядит следующим образом
# импорт коллекций
# print '' .join (collection.OrderedDict.fromkeys (string))

  
# Этот код предоставлен Bhavya Jain

C #

// C # программа для удаления дубликатов

using System;

using System.Collections.Generic;

  

class GFG

{

    / * Функция удаляет повторяющиеся символы

    из строки. Эта функция работает на месте * /

    void removeDuplicates(String str)

    {

        HashSet<char> lhs = new HashSet<char>();

        for(int i = 0; i < str.Length; i++)

            lhs.Add(str[i]);

          

        // выводим строку после удаления

        // дублирующиеся элементы

        foreach(char ch in lhs)

            Console.Write(ch);

    }

      

    // Код драйвера

    public static void Main(String []args)

    {

        String str = "geeksforgeeks";

        GFG r = new GFG();

        r.removeDuplicates(str);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

geksfor

Сложность времени: O (n)

Важные моменты:

  • Метод 1 не поддерживает порядок символов как исходная строка, но метод 2 поддерживает.
  • Предполагается, что количество возможных символов во входной строке равно 256. NO_OF_CHARS следует изменить соответствующим образом.
  • calloc используется вместо malloc для выделения памяти подсчитывающего массива (count) для инициализации выделенной памяти в '/ 0'. Также можно использовать malloc (), за которым следует memset ().
  • Вышеприведенный алгоритм также работает для входных данных целочисленного массива, если указан диапазон целых чисел в массиве. Пример проблемы — найти максимальное число встречающихся во входном массиве, учитывая, что входной массив содержит целые числа только от 1000 до 1100

Метод 5 (с помощью метода IndexOf () ):
Предварительное условие: метод Java IndexOf ()

Джава

// Java-программа тоже создает уникальную строку

import java util.*;

  

class IndexOf {

      

    // Функция, которая делает строку уникальной

    public static String unique(String s)

    {

        String str = new String();

        int len = s.length();

          

        // цикл для прохождения строки и

        // проверка повторяющихся символов с помощью

        // Метод IndexOf () в Java

        for (int i = 0; i < len; i++) 

        {

            // символ в i-ом индексе s

            char c = s.charAt(i);

              

            // если c присутствует в str, он возвращает

            // индекс c, иначе он возвращает -1

            if (str.indexOf(c) < 0)

            {

                // добавляем c в str, если возвращается -1

                str += c;

            }

        }

          

        return str;

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        // Входная строка с повторяющимися символами

        String s = "geeksforgeeks";

          

        System.out.println(unique(s));

    }

}

C #

// C # программа тоже создает уникальную строку

using System; 

      

public class IndexOf 

{

      

    // Функция, которая делает строку уникальной

    public static String unique(String s)

    {

        String str = "";

        int len = s.Length;

          

        // цикл для прохождения строки и

        // проверка повторяющихся символов с помощью

        // Метод IndexOf () в Java

        for (int i = 0; i < len; i++) 

        {

            // символ в i-ом индексе s

            char c = s[i];

              

            // если c присутствует в str, он возвращает

            // индекс c, иначе он возвращает -1

            if (str.IndexOf(c) < 0)

            {

                // добавляем c в str, если возвращается -1

                str += c;

            }

        }

          

        return str;

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        // Входная строка с повторяющимися символами

        String s = "geeksforgeeks";

          

        Console.WriteLine(unique(s));

    }

}

  
// Этот код предоставлен Принчи Сингхом


Выход :

geksfor

Спасибо debjitdbb за предложение такого подхода.

Способ 6 (с использованием метода unordered_map STL ):
Предварительное условие: метод unordered_map STL C ++

// Программа на C ++ тоже создает уникальную строку, используя unordered_map

  
/ * время доступа в unordered_map on обычно равно O (1), если нет столкновений
и, следовательно, это помогает нам проверить, существует ли элемент в строке в O (1)
временная сложность с постоянным пространством. * /

  
#include <bits/stdc++.h> 

using namespace std; 

char* removeDuplicates(char *s,int n){

  unordered_map<char,int> exists;

  int index = 0; 

  for(int i=0;i<n;i++){

    if(exists[s[i]]==0)

    {

      s[index++] = s[i];

      exists[s[i]]++;

    }

  }

  return s;

}

  
// код драйвера

int main(){

  char s[] = "geeksforgeeks";

  int n = sizeof(s)/sizeof(s[0]);

  cout<<removeDuplicates(s,n)<<endl;

  return 0;

}

Выход:

geksfor

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Спасибо Аллену Джеймсу Виной за предложение такого подхода.

Рекомендуемые посты:

Удалить дубликаты из заданной строки

0.00 (0%) 0 votes