java添加、删除和删除数组中的所有方法,而不使用任何其他数据结构或任何其他导入
我正在尝试制作一个排序数组和一些实现不同功能的方法。问题是我的作业有各种方法,我已经使用测试文件实现了这些方法来检查。作业的条件是我不能导入任何内容,我必须使用程序中可用的内容
我试着去做,也做了研究,但我无法理解。使用数组列表,它变得非常简单,但它不会有帮助
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这样的方法看起来非常简单。希望有人能把问题解释清楚。也是一种仅使用数组执行添加和删除操作的方法。还有,想知道我做错了什么吗
# 1 楼答案
在第一个构造函数中,数组的大小应该是容量。不是0。 在第二个构造函数中,数据永远不会复制到数组中。 第二个构造函数要求O(n^2),因此可以使用
Arrays.sort
的内置排序,即O(n*log(n))。 添加和删除元素必须在O(n)中,因此不能使用Arrays.sort
。只需遍历每个元素,直到找到正确的索引。在需要的地方复制数据