给定输入(items = 6, position = 3)
创建一行6 items和一个位于item 3上的字符{0,1,2,[3],4,5}
调用left()将字符移动两个item at position 3 is removed和{0,[1],2,4,5}
对right()的下一次调用将字符向右移动两个位置，item at position 1 is removed的{0,2,[4],5}
那么现在调用position()方法应该返回4。
如果没有物品，字符不会向左或向右移动，所以不需要实现。
public class MyClass {
int position;
int[] items;
public MyClass(int n, int position) {
this.position = position;
items = new int[n];
for(int i=0; i<n; i++) {
items[i] = i;
}
}
}
public void left() {
int p = this.position;
items[p] = -1;
for(int z=0; z<2;) {
p--;
int value = arr[p];
if(value != -1) {
z++;
}
}
this.position = p;
}
public void right() {
int p = this.position;
items[p] = -1;
for(int z=0; z<2;) {
p++;
int value = arr[p];
if(value != -1) {
z++;
}
}
this.position = p;
}
public int position() {
return arr[position];
}
对于小输入，这段代码工作得很好，但是当输入很大时，我得到了性能错误。
如何有效地实现这个?我没有与性能错误相关的错误的测试用例细节。
正如@AbhinavMathur在评论和回答中已经指出的那样，为了提高性能，您需要实现双链表数据结构。
注意，必须创建您自己的实现，该实现将维护对当前节点的引用。试图利用JDK中内置的实现来代替items数组不会给您带来任何好处，因为快速删除的优势将被迭代的成本所抵消(为了到达位置n的元素，LinkedList需要从头部开始爬遍n元素，并且此操作具有线性时间复杂度)。
方法left(),right()和position()将有以下结果:
-
left()—如果与current关联的前一个节点(代码中表示为prev)不是null，且其前一个节点存在，则取消对当前节点的引用(即与current节点关联的下一个节点和前一个节点相互链接)，并将变量current赋值给前一个节点的prev，即current.prev.prev。时间复杂度O(1). -
right()—如果与current相关联的下一个节点(在代码中表示为next)不是null，并且其下一个节点存在，则当前节点将以上述方式解引用，并且变量current将被分配给下一个节点的next，即current.next.next。时间复杂度O(1). -
position()-将返回current节点的值。时间复杂度O(1).
这就是它的样子:
public class MyClass {
private Node current; // a replacement for both position and items fields
public MyClass(int n, int position) {
Node current = new Node(0, null, null); // initialing the head node
if (position == 0) {
this.current = current;
}
for (int i = 1; i < n; i++) { // initialing the rest past of the linked list
Node nextNode = new Node(i, current, null);
current.setNext(nextNode);
current = nextNode;
if (position == i) {
this.current = current;
}
}
}
public void left() { // removes the current node and sets the current to the node 2 position to the left (`prev` of the `prev` node)
if (current.prev == null || current.prev.prev == null) {
return;
}
Node prev = current.prev;
Node next = current.next;
prev.setNext(next);
next.setPrev(prev);
this.current = prev.prev;
}
public void right() { // removes the current node and sets the current to the node 2 position to the right (`next` of the `next` node)
if (current.next == null || current.next.next == null) {
return;
}
Node prev = current.prev;
Node next = current.next;
prev.setNext(next);
next.setPrev(prev);
this.current = next.next;
}
public int position() {
return current.getValue();
}
public static class Node {
private int value;
private Node prev;
private Node next;
public Node(int value, Node prev, Node next) {
this.value = value;
this.prev = prev;
this.next = next;
}
// getters and setters
}
}
在线演示的链接
使用数组，您正在设置"已删除"元素为-1;在每次遍历中重复跳过它们会导致性能损失。
不使用数组，而是使用双链表。每次移除都可以在O(1)时间内轻松完成，每次左/右操作只需要将当前指针移动2个节点。