Эффективно удаляйте дубликаты из отсортированного связанного списка - PullRequest
Новая
       34

Эффективно удаляйте дубликаты из отсортированного связанного списка

0 голосов
/ 30 апреля 2020

Я нахожусь на HackerRank, и мне нужно удалить повторяющиеся элементы из отсортированного связанного списка. Я пропустил все случаи, кроме двух, которые вводятся примерно так: 10001102034 Так что моя программа занимает несколько секунд, чтобы завершить и превысить время. Как я могу сделать свой код более эффективно, я слышал об использовании квадрата root, но я не знаю, как его использовать. Любой гид ценится. Вот мой код. 

private static Node removeDuplicates(Node head) {
        /* Another reference to head */
        Node current = head;
        Node next;

        /* Traverse list till the last node */
        while (current != null && current.next != null) {
            if (current.data == current.next.data) {
                next = current.next.next;
                if (next == null) {
                    current.next = null;
                    break;
                }
                current.next = next;
            } else {
                current = current.next;
            }
        }
        return head;
    }

Снова. Это работает, но занимает слишком много времени с длинными номерами.

Ответы [ 2 ]

2 голосов
/ 30 апреля 2020

Вы должны заменить условие if (current.data == current.next.data) на while l oop и использовать break 'label': 

out:
while (current != null && current.next != null) {
    while (current.data == current.next.data) {
        next = current.next.next;
        if (next == null) {
            current.next = null;
            break out;
        }
        current.next = next;
    } 
    current = current.next;
}
0 голосов
/ 30 апреля 2020

Вы не можете использовать квадрат root, потому что, когда вы хотите удалить дубликаты из списка, вы должны проверить весь список. Метод квадрата root используется для поиска в отсортированном списке. Но на ваш вопрос, можете ли вы улучшить время выполнения для этого вашего кода в O (n ^ 2), но если вы измените свой код на использование хеш-таблицы, вы можете сделать это O (n).

import java. util.HashSet;

publi c class removeDuplicates
{stati c class class
{int val; узел следующий; 

    public node(int val)  
    { 
        this.val = val; 
    } 
} 

/* Function to remove duplicates from a 
   unsorted linked list */
static void removeDuplicate(node head)  
{ 
    // Hash to store seen values 
    HashSet<Integer> hs = new HashSet<>(); 

    /* Pick elements one by one */
    node current = head; 
    node prev = null; 
    while (current != null)  
    { 
        int curval = current.val; 

         // If current value is seen before 
        if (hs.contains(curval)) { 
            prev.next = current.next; 
        } else { 
            hs.add(curval); 
            prev = current; 
        } 
        current = current.next; 
    } 

} 

/* Function to print nodes in a given linked list */
static void printList(node head)  
{ 
    while (head != null)  
    { 
        System.out.print(head.val + " "); 
        head = head.next; 
    } 
}

Надеюсь, это поможет вам.

...