removeElement 方法和滚动元素，动态数组
removeElement method and rolling elements, Dynamic Array
我要做的是从数组中移除元素并且（因为我使用了泛型）将我移除的元素设置为空；之后我必须将元素向左滚动（例如）以擦除我以此开头的数组的空值：
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
}
我试着将元素向左滚动，但它总是留下空值！
非常感谢你的帮助，因为我不知道还能做什么；
这是完整的代码（西班牙语 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
试试这个代码
public static int removeElements(T val) {
/// Complexity: O(N)
int cantRemoved = 0;
for (int i = 0; i < arr.length; i++) {
if (val == arr[i]) {
cantRemoved++;
i++;
}
if(i < arr.length) arr[i - cantRemoved] = arr[i];
}
return cantRemoved; //Element removed
}
您开始做正确的事情，将元素移动到已删除元素的位置，但您只进行了一次移动，因此如果您删除第一个元素，您只会将 null 移动到第二个位置。所以，你需要在数组中有两个指针来处理所有的空删除权
代码应如下所示：
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;
}
我要做的是从数组中移除元素并且（因为我使用了泛型）将我移除的元素设置为空；之后我必须将元素向左滚动（例如）以擦除我以此开头的数组的空值：
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
}
我试着将元素向左滚动，但它总是留下空值！
非常感谢你的帮助，因为我不知道还能做什么；
这是完整的代码（西班牙语 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
试试这个代码
public static int removeElements(T val) {
/// Complexity: O(N)
int cantRemoved = 0;
for (int i = 0; i < arr.length; i++) {
if (val == arr[i]) {
cantRemoved++;
i++;
}
if(i < arr.length) arr[i - cantRemoved] = arr[i];
}
return cantRemoved; //Element removed
}
您开始做正确的事情，将元素移动到已删除元素的位置，但您只进行了一次移动，因此如果您删除第一个元素，您只会将 null 移动到第二个位置。所以，你需要在数组中有两个指针来处理所有的空删除权
代码应如下所示：
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;
}