数据结构，顺序表中删除第i个元素时间性能分析

请问为什么这里的有效删除位置是0~n-1呢，你n个元素为啥不能删除掉呢

下标从0开始到n-1，一共有n个元素

这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7809884
你也可以参考下这篇文章：一副从1到n的牌，每次从牌堆顶取一张放桌子上，再取一张放牌堆底，直到手中没牌，最后桌子上的牌是从1到n有序，设计程序，输入n，输出牌堆的顺序数组
除此之外, 这篇博客: 找出从1~n连续整数中的重复数字只有一个是重复的中的 下面就看代码实现： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

  public static int getDuplicateNum(int[] arr){
       if (arr.length==0) return -1;
        HashMap<Integer,Integer> map=new HashMap<>();
        int res=0;
        for (int i = 0; i <arr.length ; i++) {
            if (!map.containsKey(arr[i])){
                map.put(arr[i],i);
            }else {
                res=arr[i];
                break;
            }
        }
            return res;
}

以下回答由chatgpt基于相关博客总结生成:

问题回答：首先，我们来看一下顺序表删除第i个元素的时间复杂度。在顺序表中删除第i个元素需要将i+1到n-1位置的元素往前移动一位，然后在最后将n-1位置的元素删除，这里需要移动n-i-1个元素，所以时间复杂度为O(n-i)。而不能删除n个元素是因为n个元素的话，顺序表已经没有空余位置了，无法删除。

如果要实现删除n个元素的操作，可以考虑使用链表来存储数据，这样删除元素可以直接删除节点，不需要移动其他元素。时间复杂度为O(n)。

以C++为例，链表的实现方式如下：

#include<iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* fast = head;
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }
    if (!fast) {
        return head->next;
    }
    ListNode* slow = head;
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return head;
}

以上是删除链表中倒数第n个节点的代码，同样适用于删除链表中前n个节点，只需要将slow、fast的位置调换即可。

如果链表中的元素是对象，可以重载operator==和ostream来更方便地操作。

#include<iostream>
using namespace std;

class Node{
public:
    int val;
    Node *next;
    Node(int x) : val(x), next(NULL) {}
    friend ostream & operator<<(ostream &os, Node &node) {
        os << node.val;
        return os;
    }
    friend bool operator==(Node &node1, Node &node2) {
        return node1.val == node2.val;
    }
};

class LinkedList{
public:
    Node *head;
    LinkedList() : head(NULL){}
    void add(int val) {
        Node *newNode = new Node(val);
        if (head == NULL) {
            head = newNode;
        }
        else {
            newNode->next = head;
            head = newNode;
        }
    }
    friend ostream & operator<<(ostream &os, LinkedList &list) {
        Node *cur = list.head;
        while (cur) {
            os << *cur << " ";
            cur = cur->next;
        }
        return os;
    }
};

int main() {
    LinkedList list;
    list.add(3);
    list.add(2);
    list.add(4);
    cout << list << endl;   // 4 2 3
    Node node1(3), node2(2), node3(4);
    list.head = removeNthFromEnd(list.head, 2);
    cout << list << endl;   // 4 3
    return 0;
}

此处我们定义了LinkedList和Node两个类，重载了operator==和ostream，使操作更加方便。其中ostream & operator<<输出链表中所有节点，重载operator==用于比较节点是否相等。

最后，顺序表和链表都有各自的优缺点，在实际使用中需要根据具体的需要来选择。