What I have to do is to remove element from array and (because I used generics) set the element that I removed to null; after that I have to roll the elements to the left (for example) to erase the null of the array I started with this:
public int removeElements(T val) {
/// Complexity: O(N)
int cantRemoved = 0;
for (int i = 0; i < arr.length; i++) {
if (val == arr[i]) {
cantRemoved = cantRemoved + 1;
arr[i] = null;
}
}
return cantRemoved; //Element removed
}
I tried just to roll the element to the left but it always was leaving a null!
I'll appreciate your help, because I don't know what else do;
Here is the whole code (on spanish xd):
/*
* Puntos ejercicio: 9 (+ 2 extras)
*
* En este ejercicio, implementaremos varias operaciones de Dynamic Array:
* insertBefore(pos, A): agrega los elementos del arreglo A en la posicion pos
* removeElement(x): borra los elementos iguales a x
* get(pos): obtiene el valor en la posicion pos
* get(pos, val): asigna el valor val al elemento en la posicion pos
* resize(newCap): agranda o reduce el arreglo dinamico a la nueva capacidad
* constructor que recibe un arreglo para inicializar el dynamic array
*
* Como es un dynamic array, el arreglo debe crecer dinamicamente para acomodar
* nuevos elementos. Por otro lado, tambien debe reducirse si se borran
* elementos. Utilizar 1.5 como factor de crecimiento.
*
* Aparte del constructor y resize, no se permite crear nuevos arreglos.
*
*
* Ubiquen todas las secciones con el tag TODO. Cada tag les indicara que deben
* completar.
*
* Instrucciones adicionales:
* a) No borren los comments que existen en este codigo
* b) No se permite usar las estructuras de datos en java.util.*
* c) Se permite agregar campos adicionales en la declaracion de las clases
* d) Se permite agregar parametros adicionales a los metodos
* e) Deben cuidarse de no ejecutar operaciones ilegales (ej. accesar
* posiciones invalidas), ya sea lanzando una excepcion o retornando null
*
*/
public class DynArray<T> {
final int INITIAL_SIZE = 1; // capacidad inicial del arreglo
final double GROWTH_FACTOR = 1.5; // factor de crecimiento
private T[] arr; // arreglo que contiene los elementos
private int size; // cantidad de elementos presentes
/**
* Constructor que inicializa un arreglo dinamico vacio (sin elementos)
*/
public DynArray() {
arr = (T[]) new Object[INITIAL_SIZE];
size = 0;
}
/**
* Constructor que inicializa el arreglo dinamico en base al arreglo A que
* recibe como parametro
*/
public DynArray(T[] A) {
// TODO: implementar
// Valor: 1 punto
arr = (T[]) new Object[A.length];
for (int i = 0; i < A.length; i++) {
arr[i] = A[i];
}
size = A.length;
}
/**
* Recrea el arreglo con la nueva capacidad indicada por el parametro
* newCap. Este metodo seria usado por insertBefore() y removeElement() para
* expandir o reducir el tamanio del arreglo
*/
private void resize(int newCap) {
// TODO: implementar
// Valor: 1 punto
// Complejidad esperada: O(N) en el worst-case
T[] arrNuevo = (T[]) new Object[newCap];
for (int i = 0; i < arr.length; i++) {
arrNuevo[i] = arr[i];
}
arr = arrNuevo;
}
/**
* Inserta el contenido del arreglo A en la posicion pos Todos los elementos
* que estaban en esa posicion en adelante se ruedan hacia la derecha para
* dejar espacio a los nuevos elementos del arreglo A. Ejemplo: Si arr = [
* 1, 2, 3, 4, 5, 6 ], pos = 2 y A = [7, 8], el resultado de esta operacion
* es [ 1, 2, 7, 8, 3, 4, 5, 6 ]
*/
public void insertBefore(int pos, T[] A) { // TODO: implementar // Valor:
// 3.5 puntos // Complejidad esperada: O(N) en el worst-case
if (arr.length < (size + A.length))
resize((int) ((size + A.length) * GROWTH_FACTOR));
for (int i = size - 1; i >= pos; i--) {
arr[i + A.length] = arr[i];
}
size = size + A.length;
for (int i = pos, j = 0; i <= A.length + 1; i++, j++) {
arr[i] = A[j];
}
}
/**
* Elimina todos los elementos cuyo valor sea igual a val, dejando todos los
* demas elementos en el mismo orden original, pero rodados hacia la
* izquierda para ocupar los espacios borrados. Retorna la cantidad de
* elementos borrados. Ejemplo: Si arr = [ 1, 2, 3, 4, 2, 2, 0, 1, 5 ] y val
* = 2, el arreglo dinamico termina con la secuencia [ 1, 3, 4, 0, 1, 5 ] y
* esta operacion devuelve 3 Si no existe un elemento con valor val,
* devuelve 0
*/
public int removeElements(T val) {
// TODO: implementar
// Valor: 2.5 puntos
// Complejidad esperada: O(N)
int pos = 0;
int cantRemovidos = 0;
for (int i = 0; i < arr.length; i++) {
if (val == arr[i]) {
cantRemovidos = cantRemovidos + 1;
arr[i] = arr[i + 1];
}
}
return cantRemovidos;
}
/**
* Retorna el valor en la posicion pos del arreglo
*/
public T get(int pos) {
// TODO: implementar
// Valor: 0.5 puntos
return arr[pos];
}
/**
* Asigna el valor val al elemento en la posicion pos del arreglo
*/
public void set(int pos, T val) {
// TODO: implementar
// Valor: 0.5 puntos
arr[pos] = val;
}
/**
* Convierte el arreglo a String para imprimir en la consola
*/
@Override
public String toString() {
StringBuffer res = new StringBuffer();
res.append("[");
for (int i = 0; i < size; i++) {
if (i > 0)
res.append(", ");
else
res.append(" ");
res.append(arr[i]);
}
res.append(" ]");
return res.toString();
}
public static void main(String[] args) {
DynArray A = new DynArray(new Integer[] { 4, 2, 2, 3, 0, 5, -1, -3, 1 });
// A.insertBefore( 2, new Integer[] { 3, 4, 1} );
System.out.println(A);
int nRemoved = A.removeElements(3);
System.out.println("Number of removed elements: " + nRemoved);
System.out.println(A);
}
}
// TODO: Modifica la clase DynArray para que utilice Generics de Java.
// Tambien deben modificar el metodo main() de la clase Lab1d
// Valor: 2 puntos extras
You're starting to do right thing by shifting elements to position of deleted element, but you're doing shift only once, so if you're deleting first element, you'll have null shifted only to the second position. So, you need to have two pointers in array to handle all null deletion right
Code should look like this:
public int removeElements(T val) {
// TODO: implementar
// Valor: 2.5 puntos
// Complejidad esperada: O(N)
int cantRemovidos = 0;
for (int i = 0, j = 0; i < arr.length; i++) {
if (val == arr[i]) {
cantRemovidos = cantRemovidos + 1;
} else {
arr[j] = arr[i]; // keeping the item
j++; // shifting second pointer
}
}
size = size - cantRemovidos; // maintain size, here you can perform array shrink
return cantRemovidos;
}