Найти уникальный Arraylist в ArrayList из ArrayLists

Как я понимаю, класс ArrayList наследует функцию equals() его родительского класса List, чтобы найти, являются ли два объекта-члена одинаковыми. Означает ли это, что 'содержит()' линейный поиск (используя 'equal') для двойной записи в ArrayList? Таким образом, сложность «содержит» - это O (n)?Найти уникальный Arraylist в ArrayList из ArrayLists

Если я использую ArrayList Arraylist, тогда сложность функции содержит O (n * m)? Если да, то есть ли какая-либо замена содержит функцию, которая может получить некоторый хеш (на основе содержимого) члена ArrayList и подтвердить, что два объекта ArrayList равны?

Редактировать: Я просто пытаюсь найти количество уникальных элементов в ArrayList из ArrayList. Например {{0,0,3}, {1,2,3}, {0,0,3}} должны давать {{0,0,3}, {1,2,3}}.

источник

2014-01-03 Mangat Rai Modi

Ваше понимание верное. Вам нужно будет написать метод замены и хэш-функцию самостоятельно. –

Вы можете получить логарифмическую производительность, если сортируете список, а затем используете двоичный поиск. Но нормальный содержит метод линейный. –

Существуют более подходящие структуры данных для 'contains', такие как' HashSet', но для получения более подробной информации о том, что вы пытаетесь сделать (как и для сторонних сторон). Установки по определению не содержат дубликатов. –

Если у вас уже есть ArrayList<ArrayList<Integer>> вы можете передать его в HashSet<ArrayList<Integer>> «s конструктора и имеют уникальный набор ArrayLists

List<ArrayList<Integer>> mylist_list = new ArrayList<ArrayList<Integer>>(); 
ArrayList<Integer> mylist = new ArrayList<Integer>(); 
... 
for(ArrayList<Integer> list : mylist_list) 
{ 
    System.out.println(Arrays.toString(list.toArray())); 
} 
Set<ArrayList<Integer>> mylist_set = new HashSet<ArrayList<Integer>>(mylist_list); 

for(ArrayList<Integer> list : mylist_set) 
{ 
    System.out.println(Arrays.toString(list.toArray()));    
}

Поддавшись выход

[0, 1, 2] 
[0, 1, 2] 
[0, 1, 2]

При переходе дубликатов в ArrayList<ArrayList<Integer>>

источник

2014-01-03 21:45:15

Я собирался попросить вас ответить на него. Спасибо за помощь! –

Нет проблем! Конечно, вы хотите построить HashSet для начала, если вам нужны только уникальные возможности: –

@ C.B. Можете ли вы ответить на вопрос Алекса выше? –

Сложность - O (N). Реализация следующий:

public int indexOf(Object o) { 
    if (o == null) { 
     for (int i = 0; i < size; i++) 
      if (elementData[i]==null) 
       return i; 
    } else { 
     for (int i = 0; i < size; i++) 
      if (o.equals(elementData[i])) 
       return i; 
    } 
    return -1; 
}

да, contains звонков indexOf метода.

источник

2014-01-03 21:23:40

Найти уникальный Arraylist в ArrayList из ArrayLists

ответ

Смежные вопросы