java - 添加，删除和删除数组中的所有方法，而不使用任何其他数据结构或任何其他导入

Question

我正在尝试制作一个排序数组和一些方法来执行不同的功能。问题是我的作业有各种方法，我已经使用测试文件来检查这些方法。作业的条件是我不能导入任何东西，我必须使用程序中可用的东西

我试着去做，也做了研究，但我无法弄清楚。使用数组列表，它变得非常简单，但它无济于事。

import java.util.Arrays;
import java.util.Iterator;

public class SortedArray<T extends Comparable> implements java.lang.Iterable<T> {

/** Constructor: constructs and empty OrderedArray with an initial capacity
 * as given.
 * 
 * Complexity: the time complexity of this operation must be O(1).
 * 
 * @param capacity initial capacity
 */


public SortedArray(int capacity) {

this.array = (T[]) new Comparable[0];
this.capacity = capacity;
this.size = 0;


}

/** Constructs an ordered array from an (unordered) array. The
 * initial capacity of the array should either be capacity, or the size of
 * data, whichever is larger.
 * 
 * Complexity: the time complexity of this operation must be O(n^2) in the 
 * size of data.
 * 
 * @param capacity initial capacity of the array
 * @param data elements to populate the array with
 */
public SortedArray(int capacity, T[] data) {


    if(capacity > data.length)
    {
    this.capacity = capacity;
    }
    else {
            this.capacity = data.length;
            }
    this.size = data.length;

    this.array = (T[]) new Comparable[0];

}


/** Returns the current size of the array (number of elements 
 * inserted, minus number of elements removed).
 * 
 * Complexity: the time complexity of this method must be O(1).
 * 
 * @return Size of the array  
 */
final public int size() {      

    return this.size;

    }

/** Returns the capacity (maximum size) of the array.
 * 
 * Complexity: the time complexity of this method must be O(1).
 * 
 * @return Capacity of the array
 */
final public int capacity() {


    return this.capacity;
}

/** Returns true if the array is empty (size is 0).
 * 
 * Complexity: the time complexity of this method must be O(1).
 * 
 * @return true if the array is empty
 */
final boolean isEmpty() {


        return array.length == 0;

}

/** Returns true if the array is full (size = capacity).
 * 
 * Complexity: the time complexity of this method must be O(1).
 * 
 * @return true if the array is full
 */
final boolean isFull() {


        return size == capacity;

}

/** Adds an element to the array, by inserting it at the proper
 * location. Note that duplicate elements can be added.
 * 
 * If the array is full(), nothing should be inserted, and the array's
 * contents should be unchanged.
 * 
 * Complexity: the time complexity of this method must be O(n) in the size()
 * of the array.
 * 
 * @param element to be added
 */


final void add(T element) {

    if(this.array.length != this.capacity){
           this.indexOf(element);
    }

    Arrays.sort(this.array);


}



/** Removes the specified element from the array, if it
 * exists. If the element does not exist, does nothing.
 * 
 * Complexity: the time complexity of this method must be O(n) in the size
 * of the array.
 * 
 * @param element to be removed 
 * 
 */
final void remove(T element) {


   for(int i =0; i<this.size;i++){
       if(this.array[i] == element)
           this.indexOf(element);
    }
}      




/** Removes all elements from the array.
 */
final void clear() {


    this.clear();


}


@Override
final public Iterator<T> iterator() {
    // Do not modify this method.
    return Arrays.stream(array).iterator();
}

// Do not modify these data members.
final private T[] array;     // Storage for the array's element
private int size;      // Current size of the array
final private int capacity;  // Maximum size of the array

 }

我得到的结果是我的测试失败了，但是构造函数和容量测试有效。只是不知道为什么其他方法会失败，因为 size、isFull 和 isEmpty 等方法似乎很简单。希望有人可以解释问题彻底。也是一种仅使用数组来执行添加和删除操作的方法。另外，想知道我做错了什么

标签： javaarrays

Answer 1

在第一个构造函数中，数组的大小应该是容量。不是 0。在第二个构造函数中，您的数据永远不会复制到数组中。Arrays.sort第二个构造函数要求 O(n^2)，因此您可以使用O(n*log(n))的内置排序。添加和删​​除元素必须在 O(n) 中，因此不能使用Arrays.sort. 只需遍历每个元素，直到找到正确的索引。在需要的地方复制数据。

import java.util.Arrays;
import java.util.Iterator;

@SuppressWarnings("unchecked")
public class SortedArray<T extends Comparable> implements java.lang.Iterable<T> {

    /**
     * Constructor: constructs and empty OrderedArray with an initial capacity
     * as given.
     * <p>
     * Complexity: the time complexity of this operation must be O(1).
     *
     * @param capacity initial capacity
     */
    public SortedArray(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException();
        }

        this.array = (T[]) new Comparable[capacity];
        this.capacity = capacity;
        this.size = 0;
    }

    /**
     * Constructs an ordered array from an (unordered) array. The
     * initial capacity of the array should either be capacity, or the size of
     * data, whichever is larger.
     * <p>
     * Complexity: the time complexity of this operation must be O(n^2) in the
     * size of data.
     *
     * @param capacity initial capacity of the array
     * @param data     elements to populate the array with
     */
    public SortedArray(int capacity, T[] data) {
        if (capacity < 0) {
            throw new IllegalArgumentException();
        }

        if (capacity > data.length) {
            this.capacity = capacity;
        } else {
            this.capacity = data.length;
        }
        this.size = data.length;

        this.array = Arrays.copyOf(data, this.size);
        Arrays.sort(this.array);
    }


    /**
     * Returns the current size of the array (number of elements
     * inserted, minus number of elements removed).
     * <p>
     * Complexity: the time complexity of this method must be O(1).
     *
     * @return Size of the array
     */
    final public int size() {
        return size;
    }

    /**
     * Returns the capacity (maximum size) of the array.
     * <p>
     * Complexity: the time complexity of this method must be O(1).
     *
     * @return Capacity of the array
     */
    final public int capacity() {
        return capacity;
    }

    /**
     * Returns true if the array is empty (size is 0).
     * <p>
     * Complexity: the time complexity of this method must be O(1).
     *
     * @return true if the array is empty
     */
    final boolean isEmpty() {
        return size == 0;
    }

    /**
     * Returns true if the array is full (size = capacity).
     * <p>
     * Complexity: the time complexity of this method must be O(1).
     *
     * @return true if the array is full
     */
    final boolean isFull() {
        return size == capacity;
    }

    /**
     * Adds an element to the array, by inserting it at the proper
     * location. Note that duplicate elements can be added.
     * <p>
     * If the array is full(), nothing should be inserted, and the array's
     * contents should be unchanged.
     * <p>
     * Complexity: the time complexity of this method must be O(n) in the size()
     * of the array.
     *
     * @param element to be added
     */
    final void add(T element) {
        if (isFull()) {
            return;
        }
        if (element == null) {
            throw new NullPointerException();
        }

        int insertAt = 0;
        for (; insertAt < size; insertAt++) {
            if (element.compareTo(array[insertAt]) < 0) {
                break;
            }
        }

        if (size - 1 - insertAt >= 0) {
            System.arraycopy(array, insertAt, array, insertAt + 1, size - insertAt);
        }
        array[insertAt] = element;
        size++;
    }

    /**
     * Removes the specified element from the array, if it
     * exists. If the element does not exist, does nothing.
     * <p>
     * Complexity: the time complexity of this method must be O(n) in the size
     * of the array.
     *
     * @param element to be removed
     */
    final void remove(T element) {
        if (isEmpty() || element == null) {
            return;
        }

        int removeAt = 0;
        for (; removeAt < size; removeAt++) {
            if (array[removeAt].compareTo(element) == 0) {
                break;
            }
        }

        if (removeAt < size) {
            System.arraycopy(array, removeAt + 1, array, removeAt, size - removeAt - 1);
            array[size - 1] = null;
            size--;
        }
    }


    /**
     * Removes all elements from the array.
     */
    final void clear() {
        for (int i = 0; i < size; i++) {
            array[i] = null;
        }
    }

    @Override
    final public Iterator<T> iterator() {
        // Do not modify this method.
        return Arrays.stream(array).iterator();
    }

    // Do not modify these data members.
    final private T[] array;     // Storage for the array's element
    private int size;      // Current size of the array
    final private int capacity;  // Maximum size of the array
}