Как проверить, достаточно ли массива в java?

Question

Я хочу проверить, заполнен ли массив 75% объектами, и если это правда, я должен изменить его размер. В переменной size у меня есть свои объекты (! = NULL) и у меня есть массив целых чисел ints

public class PQ { 

private int[] pq; 
private int size; 

public PQ(int capacity) { 
    if (capacity < 1) { 
     throw new IllegalArgumentException(); 
    } 
    this.pq = new int[capacity + 1]; 
    this.size = 0; 
} 

public void insert(int number) { 
      //Code 
} 


private int[] resize() { 
    int[] newPQ = new int[this.pq.length * 2]; 
    for (int i = 0; i < this.pq.length; i++) { 
     newPQ[i] = this.pq[i]; 
    } 
    return newPQ; 
} 
} 

Answer 1

Попробуйте это:

Всякий раз, когда вы добавляете элемент, мы увеличиваем size (это будет отслеживать количество непустых пространств, так что вам не нужно постоянно пересчитывать массив). Затем мы сравниваем это число с общей длиной вашего массива. Если count не менее 75% от размера массива, мы вызываем ваш метод изменения размера и устанавливаем pq в новый массив, который он возвращает. Я предполагаю, что вы хотите добавить в конец массива и что вам не нужны пустые индексы между числами. Если вам нужны пробелы, вам нужно будет использовать цикл, который я пытаюсь избежать ради эффективности, если это не обязательно. Предполагая, что вы этого не сделали, вы можете просто добавить в свой массив индекс size, так как это будет первый непустой элемент.

//O(1) efficiency if you don't need to resize, O(n) if you do 

public void insert(int number) { 
     if(size/pq.length >= 75) { 
      pq = resize(); 
     } 
     pq[size] = number; //Since this will be the first non-empty index 
     size++; 
     return; //Doing it this way, if you can, is much more efficient than looping 
} 

Если вы звоните удалить и вывезти из ничего, но в конце вы будете иметь, чтобы переместить все вниз, так что у вас нет пустого пространства.

Если у вас есть пустые индексы, попробуйте что-то вроде этого (чтобы вставить в первый пустой индекс, столкнувшись с циклом) ... Давайте вместо этого используем Integer [], чтобы вы могли проверить значение null и надеть ' t нужно беспокоиться о том, что любые 0 в массиве считаются пустыми (int [] инициирует все до 0). Таким образом, мы можем проверить пустое место, а 0 не считаются пустыми, если вы используете их в своем int[].

//O(n) efficiency if you don't need to resize, O(n^2) if you do 

    public void insert(int number) { 
      if(size/pq.length >= 75) { 
       pq = resize(); 
       //You would have to make resize return an Integer[] and 
       //implement this throughout the code 
      } 
      for(int i = 0; i < pq.length; i++) { 
       if(pq[i] == null) { 
        pq[size] = number; 
        size++; 
        return; 
       } 
      } 
    } 

Независимо: Помните, когда вы звоните remove() декрементировать size.

Answer 2

Что вы можете сделать, это иметь переменное число экземпляров под названием счетчик, который отслеживает количество элементов в массив pq. И всякий раз, когда вы вставляете элемент в массив через метод insert, вы можете увеличить значение счетчика. Всякий раз, когда вы удаляете элемент из массива методом удаления, вы можете уменьшить значение счетчика. Затем вы можете использовать это, чтобы проверить, если массив 75% заполнен, по меньшей мере,

if(pq.length * .75 <= size){ 
    //do what you need to do here 
} 

И класс будет выглядеть так,

public class PQ { 

private int[] pq; 
private int size; 


public PQ(int capacity) { 
    if (capacity < 1) { 
     throw new IllegalArgumentException(); 
    } 
    this.pq = new int[capacity + 1]; 
    this.size = 0; 

} 

public void insert(int number) { 
      size++; 
      //Code 
} 
public void remove(int number) { 
      size--; 
      //Code 
} 

private int[] resize() { 
    int[] newPQ = new int[this.pq.length * 2]; 
    for (int i = 0; i < this.pq.length; i++) { 
     newPQ[i] = this.pq[i]; 
    } 
    return newPQ; 
} 
} 

Answer 3

Вы явно сохраняете размер как переменную. Вы также знаете размер поддерживающего массива. Сравните их в точке, когда вам нужно проверить размер: if(this.size > 3*this.pq/4).

Answer 4

Использование ArrayList делает все автоматически для вас более эффективным способом.

Отредактировано:

это инициализация, все положить -1

this.pq = new int[capacity + 1]; 
Arrays.fill(pq, -1); 

тогда, когда вы проверяете вы делаете так:

if(pq[pq.length*.75] != -1) { 
    // then is means that is has already filled up 75% 
} else { 
    // not filled 75% yet 
}