從數組中刪除一個元素（使用兩次遍歷和一次遍歷） · GeeksForGeeks 中文系列教程

# 從數組中刪除一個元素（使用兩次遍歷和一次遍歷） > 原文： [https://www.geeksforgeeks.org/delete-an-element-from-array-using-two-traversals-and-one-traversal/](https://www.geeksforgeeks.org/delete-an-element-from-array-using-two-traversals-and-one-traversal/) 給定一個數組和一個數字“ x”，編寫一個函數從給定的數組中刪除“ x”。我們假設數組維護著兩件事，容量和大小。因此，當我們刪除一個項目時，容量不會改變，只有大小會改變。 **示例**： ``` Input: arr[] = {3, 1, 2, 5, 90}, x = 2, size = 5, capacity = 5 Output: arr[] = {3, 1, 5, 90, _}, size = 4, capacity = 5 Input: arr[] = {3, 1, 2, _, _}, x = 2, size = 3, capacity = 5 Output: arr[] = {3, 1, _, _, _}, size = 4, capacity = 5 ``` **方法 1（先搜索，然后刪除）** 我們首先在數組中搜索“ x”，然后在 x 右側的元素向后搜索一個位置。以下是此簡單方法的實現。 ## C/C++ ``` // C++ program to remove a given element from an array #include<bits/stdc++.h> using namespace std; // This function removes an element x from arr[] and // returns new size after removal (size is reduced only // when x is present in arr[] int deleteElement(int arr[], int n, int x) { ???// Search x in array ???int i; ???for (i=0; i<n; i++) ??????if (arr[i] == x) ?????????break; ???// If x found in array ???if (i < n) ???{ ?????// reduce size of array and move all ?????// elements on space ahead ?????n = n - 1; ?????for (int j=i; j<n; j++) ????????arr[j] = arr[j+1]; ???} ???return n; } /* Driver program to test above function */ int main() { ????int arr[] = {11, 15, 6, 8, 9, 10}; ????int n = sizeof(arr)/sizeof(arr[0]); ????int x = 6; ????// Delete x from arr[] ????n = deleteElement(arr, n, x); ????cout << "Modified array is \n"; ????for (int i=0; i<n; i++) ???????cout << arr[i] << " "; ????return 0; } ``` ## Java ```java // Java program to remove a given element from an array import java.io.*; class Deletion { ????// This function removes an element x from arr[] and ????// returns new size after removal (size is reduced only ????// when x is present in arr[] ????static int deleteElement(int arr[], int n, int x) ????{ ????????// Search x in array ????????int i; ????????for (i=0; i<n; i++) ????????????if (arr[i] == x) ????????????????break; ????????// If x found in array ????????if (i < n) ????????{ ????????????// reduce size of array and move all ????????????// elements on space ahead ????????????n = n - 1; ????????????for (int j=i; j<n; j++) ????????????????arr[j] = arr[j+1]; ????????} ????????return n; ????} ????// Driver program to test above function ????public static void main(String[] args) ????{ ????????int arr[] = {11, 15, 6, 8, 9, 10}; ????????int n = arr.length; ????????int x = 6; ????????// Delete x from arr[] ????????n = deleteElement(arr, n, x); ????????System.out.println("Modified array is"); ????????for (int i = 0; i < n; i++) ????????????System.out.print(arr[i]+" "); ????} } /*This code is contributed by Devesh Agrawal*/ ``` ## Python3 ```py # Python 3 program to remove a given? # element from an array # This function removes an element x? # from arr[] and returns new size after? # removal (size is reduced only when x? # is present in arr[] def deleteElement(arr, n, x): ????# Search x in array ????for i in range(n): ????????if (arr[i] == x): ????????????break ????# If x found in array ????if (i < n): ????????# reduce size of array and move? ????????# all elements on space ahead ????????n = n - 1; ????????for j in range(i, n, 1): ????????????arr[j] = arr[j + 1] ????return n # Driver Code if __name__ == '__main__': ????arr = [11, 15, 6, 8, 9, 10] ????n = len(arr) ????x = 6 ????# Delete x from arr[] ????n = deleteElement(arr, n, x) ????print("Modified array is") ????for i in range(n): ????????print(arr[i], end = " ") # This code is contributed by # Shashank_Sharma ``` ## C# ```cs // C# program to remove a given element from // an array using System; class GFG { ????// This function removes an element x ????// from arr[] and returns new size? ????// after removal (size is reduced only ????// when x is present in arr[] ????static int deleteElement(int []arr, ??????????????????????????????int n, int x) ????{ ????????// Search x in array ????????int i; ????????for (i = 0; i < n; i++) ????????????if (arr[i] == x) ????????????????break; ????????// If x found in array ????????if (i < n) ????????{ ????????????// reduce size of array and ????????????// move all elements on? ????????????// space ahead ????????????n = n - 1; ????????????for (int j = i; j < n; j++) ????????????????arr[j] = arr[j+1]; ????????} ????????return n; ????} ????// Driver program to test above function ????public static void Main() ????{ ????????int []arr = {11, 15, 6, 8, 9, 10}; ????????int n = arr.Length; ????????int x = 6; ????????// Delete x from arr[] ????????n = deleteElement(arr, n, x); ????????Console.WriteLine("Modified array is"); ????????for (int i = 0; i < n; i++) ????????????Console.Write(arr[i]+" "); ????} } // This code is contributed by nitin mittal. ``` **輸出**： ``` Modified array is 11 15 8 9 10 ``` **方法 2（在搜索時移動元素）** 此方法假定元素始終存在于數組中。這個想法是從最右邊的元素開始，并在搜索“ x”時保持元素不斷移動。以下是此方法的 C++ 和 Java 實現。請注意，當數組中不存在“ x”時，此方法可能會產生意外結果。 ## C++ ```cpp // C++ program to remove a given element from an array #include<iostream> using namespace std; // This function removes an element x from arr[] and // returns new size after removal. // Returned size is n-1 when element is present. // Otherwise 0 is returned to indicate failure. int deleteElement(int arr[], int n, int x) { ???// If x is last element, nothing to do ???if (arr[n-1] == x) ???????return (n-1); ???// Start from rightmost element and keep moving ???// elements one position ahead. ???int prev = arr[n-1], i; ???for (i=n-2; i>=0 && arr[i]!=x; i--) ???{ ???????int curr = arr[i]; ???????arr[i] = prev; ???????prev = curr; ???} ???// If element was not found ???if (i < 0) ?????return 0; ???// Else move the next element in place of x ???arr[i] = prev; ???return (n-1); } /* Driver program to test above function */ int main() { ????int arr[] = {11, 15, 6, 8, 9, 10}; ????int n = sizeof(arr)/sizeof(arr[0]); ????int x = 6; ????// Delete x from arr[] ????n = deleteElement(arr, n, x); ????cout << "Modified array is \n"; ????for (int i=0; i<n; i++) ???????cout << arr[i] << " "; ????return 0; } ``` ## Java ```java // Java program to remove a given element from an array import java.io.*; class Deletion { ????// This function removes an element x from arr[] and ????// returns new size after removal. ????// Returned size is n-1 when element is present. ????// Otherwise 0 is returned to indicate failure. ????static int deleteElement(int arr[], int n, int x) ????{ ????????// If x is last element, nothing to do ????????if (arr[n-1] == x) ????????????return (n-1); ????????// Start from rightmost element and keep moving ????????// elements one position ahead. ????????int prev = arr[n-1], i; ????????for (i=n-2; i>=0 && arr[i]!=x; i--) ????????{ ????????????int curr = arr[i]; ????????????arr[i] = prev; ????????????prev = curr; ????????} ????????// If element was not found ????????if (i < 0) ????????????return 0; ????????// Else move the next element in place of x ????????arr[i] = prev; ????????return (n-1); ????} ????// Driver program to test above function ????public static void main(String[] args) ????{ ????????int arr[] = {11, 15, 6, 8, 9, 10}; ????????int n = arr.length; ????????int x = 6; ????????// Delete x from arr[] ????????n = deleteElement(arr, n, x); ????????System.out.println("Modified array is"); ????????for (int i = 0; i < n; i++) ????????????System.out.print(arr[i]+" "); ????} } /*This code is contributed by Devesh Agrawal*/ ``` ## Python3 ```py # python program to remove a given element from an array? # This function removes an element x from arr[] and? # returns new size after removal.? # Returned size is n-1 when element is present.? # Otherwise 0 is returned to indicate failure.? def deleteElement(arr,n,x): ????# If x is last element, nothing to do? ????if arr[n-1]==x: ????????return n-1 ????# Start from rightmost element and keep moving? ???# elements one position ahead.? ????prev = arr[n-1] ????for i in range(n-2,1,-1): ????????if arr[i]!=x: ????????????curr = arr[i] ????????????arr[i] = prev ????????????prev = curr ????# If element was not found? ????if i<0: ????????return 0 ????# Else move the next element in place of x? ????arr[i] = prev ????return n-1 # Driver code arr = [11,15,6,8,9,10] n = len(arr) x = 6 n = deleteElement(arr,n,x) print("Modified array is") for i in range(n): ????print(arr[i],end=" ") # This code is contributed by Shrikant13 ``` ## C# ``` // C# program to remove a given // element from an array using System; class GFG { ????// This function removes an ????// element x from arr[] and ????// returns new size after? ????// removal. Returned size is ????// n-1 when element is present. ????// Otherwise 0 is returned to? ????// indicate failure. ????static int deleteElement(int []arr,? ?????????????????????????????int n,? ?????????????????????????????int x) ????{ ????????// If x is last element, ????????// nothing to do ????????if (arr[n - 1] == x) ????????????return (n - 1); ????????// Start from rightmost? ????????// element and keep moving ????????// elements one position ahead. ????????int prev = arr[n - 1], i; ????????for (i = n - 2; i >= 0 && ????????????????arr[i] != x; i--) ????????{ ????????????int curr = arr[i]; ????????????arr[i] = prev; ????????????prev = curr; ????????} ????????// If element was? ????????// not found ????????if (i < 0) ????????????return 0; ????????// Else move the next? ????????// element in place of x ????????arr[i] = prev; ????????return (n - 1); ????} ????// Driver Code? ????public static void Main() ????{ ????????int []arr = {11, 15, 6, 8, 9, 10}; ????????int n = arr.Length; ????????int x = 6; ????????// Delete x from arr[] ????????n = deleteElement(arr, n, x); ????????Console.WriteLine("Modified array is"); ????????for(int i = 0; i < n; i++) ????????????Console.Write(arr[i]+" "); ????} } // This code is contributed by anuj_67\. ``` **輸出**： ``` Modified array is 11 15 8 9 10 ``` 即使給定要刪除元素的索引，從數組中刪除元素也需要`O(n)`時間。對于排序數組，時間復雜度也保持為`O(n)`。在鏈表中，如果我們知道指向要刪除的節點的上一個節點的指針，則可以在`O(1)`時間進行刪除。