下面有四个问题:
- 把数组元素前后部分交换 MoveFirstPartOfArrayToTheEnd(int[] array, int index) 比如 {1,2,3,4,5,6,7} 3 => {4,5,6,7,1,2,3}
- 把数组元素前后部分交换 MoveFirstPartOfArrayToTheEnd(int[] array, int value）比如 {1,2,8,4,5,6,7} 8 => {4,5,6,7,1,2,8}
- 把数组一段移动到后面MoveSomeElementsToTheEnd(int[] array, int startIndex, int length)比如{1,2,3,4,5,6,7,8} 3 3 => {1,2,3,7,8,4,5,6}
- 把数组中重复的元素变成0放到最后面RemoveDulplicatedElements(int[] array) 比如 {1,3,3,2,4,4,4,5} => {1,3,2,4,5,0,0,0}
你首先想到的办法是什么？
- 申请一个临时数组把FistPart和EndPart交换
- 同上，只要找到对应值的下标即可。
- 同上申请临时数组，把要移动的段放到临时数组里
- 申请一个临时的List<int>把唯一的元素加到List里面，再重新赋给Array。
1 class Program 2 { 3 static void Main(string[] args) 4 { 5 //1 6 int[] array1 = { 1, 2, 3, 4, 5, 6, 7 }; 7 MoveFirstPartOfArrayToTheEnd(array1, 3); 8 printArray(array1); 9 10 //2 11 int[] array2 = { 1, 2, 8, 4, 5, 6, 7 }; 12 MoveFirstPartOfArrayToTheEndValue(array2, 8); 13 printArray(array2); 14 15 //3 16 int[] array3 = { 1, 2, 3, 4, 5, 6, 7, 8 }; 17 MoveSomeElementsToTheEnd(array3, 3, 3); 18 printArray(array3); 19 20 //4 21 int[] array4 = { 1, 3, 3, 2, 4, 4, 4, 5 }; 22 removeDulplicatedElements(array4); 23 printArray(array4); 24 25 } 26 27 private static void printArray(int[] array) 28 { 29 for (int i = 0; i < array.Length; i++) 30 { 31 Console.Write(array[i]); 32 } 33 Console.WriteLine(); 34 } 35 36 public static void MoveFirstPartOfArrayToTheEnd(int[] array, int index) 37 { 38 if (index >= array.Length || index <= 0) 39 { 40 throw new Exception("index must be greater than 0 and less than " + array.Length); 41 } 42 43 //Move the first part of array to a temp array 44 int[] temp = new int[index]; 45 for (int i = 0; i < index; i++) 46 { 47 temp[i] = array[i]; 48 } 49 50 //Move forward the other element 51 for (int i = 0; i < array.Length - index; i++) 52 { 53 array[i] = array[i + index]; 54 } 55 56 //Move the first part back to the end of array 57 int j = 0; 58 for (int i = array.Length - index; i < array.Length; i++) 59 { 60 array[i] = temp[j]; 61 j++; 62 } 63 } 64 65 public static void MoveFirstPartOfArrayToTheEndValue(int[] array, int value) 66 { 67 bool move = false; 68 69 //Search the value in the array 70 for (int i = 0; i < array.Length; i++) 71 { 72 if (array[i] == value) 73 { 74 75 //Move the first part if we find the value 76 MoveFirstPartOfArrayToTheEnd(array, i + 1); 77 move = true; 78 break; 79 } 80 } 81 82 if (!move) 83 { 84 throw new Exception("No matched value is found in the array"); 85 } 86 } 87 88 public static void MoveSomeElementsToTheEnd(int[] array, int startIndex, int length) 89 { 90 if (startIndex < 0 || startIndex >= array.Length - 1) 91 { 92 throw new Exception("startIndex must be greater than 0 and less than " + (array.Length - 1).ToString()); 93 } 94 95 if (startIndex + length + 1 > array.Length) 96 { 97 throw new Exception("Please provide a valid length"); 98 } 99 100 int[] temp = new int[length]; 101 for (int i = 0; i < temp.Length; i++) 102 { 103 temp[i] = array[startIndex + i]; 104 } 105 106 //Move forward the other element 107 for (int i = startIndex; i < array.Length - length; i++) 108 { 109 array[i] = array[i + length]; 110 } 111 112 //Move the first part back to the end of array 113 int k = 0; 114 for (int i = array.Length - length; i < array.Length; i++) 115 { 116 array[i] = temp[k]; 117 k++; 118 } 119 } 120 121 public static void removeDulplicatedElements(int[] array) 122 { 123 List<int> temp = new List<int>(); 124 for (int i = 0; i < array.Length; i++) 125 { 126 if (array[i] == 0) 127 continue; 128 temp.Add(array[i]); 129 for (int j = i + 1; j < array.Length; j++) 130 { 131 if (array[i] == array[j]) 132 { 133 array[j] = 0; 134 } 135 } 136 } 137 138 for (int i = 0; i < array.Length; i++) 139 { 140 if (i < temp.Count) 141 { 142 array[i] = temp[i]; 143 } 144 else 145 { 146 array[i] = 0; 147 } 148 } 149 } 150 }
现在要求优化算法，空间复杂度为O（1），该如何去优化呢？
- 我们先看{1，2，3，4，5，6，7}3如何变成{4，5，6，7，1，2，3}的，首先前后部分各自反转变成{3，2，1，7，6，5，4}然后再把整个数组反转就变成了{4，5，6，7，1，2，3}。
- 同上，只要找到对应值的下标即可。
- 我们再看{1,2,3,4,5,6,7,8} 3 3 => {1,2,3,7,8,4,5,6}过程，前面不动的部分{1,2,3}先不管，且看后面{4,5,6,7,8}=>{7,8,4,5,6},同上面，各自反转尔后整体反转{6，5，4，8，7}=>{7,8,4,5,6}
- {1,3,3,2,4,4,4,5} => {1,3,2,4,5,0,0,0}的过程，先把重复的元素变成0，再依次移动到最后，{1,3,3,2,4,4,4,5} => {1,3,0,2,4,0,0,5}=>{1,3,2,4,0,0,5,0}=>{1,3,2,4,0,5,0,0}=>{1,3,2,4,5,0,0,0}
从上面可以看出都用到了一个通用的方法就是反转数组ReversArray().这个操作只需要申请一个临时变量。即空间复杂度为O(1)
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6 7 namespace TransposeArray 8 { 9 class Program 10 { 11 static void Main(string[] args) 12 { 13 //1 {1,2,3,4,5,6,7} 3 => {4,5,6,7,1,2,3} 14 int[] Array1 = new int[] { 1, 2, 3, 4, 5, 6, 7 }; 15 TransposeByIndex(Array1, 3); 16 PrintArray(Array1); 17 //2 {1,2,8,4,5,6,7} 8 => {4,5,6,7,1,2,8} 18 int[] Array2 = new int[] { 1, 2, 8, 4, 5, 6, 7 }; 19 TransposeByValue(Array2, 8); 20 PrintArray(Array2); 21 //3 {1,2,3,4,5,6,7,8} 3 3 => {1,2,3,7,8,4,5,6} 22 int[] Array3 = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 }; 23 TransposeBySegment(Array3, 3, 3); 24 PrintArray(Array3); 25 //4 {1,3,3,2,4,4,4,5} => {1,3,2,4,5,0,0,0} 26 int[] Array4 = new int[] { 1, 3, 3, 2, 4, 4, 4, 5 }; 27 RemoveDuplicated(Array4); 28 PrintArray(Array4); 29 } 30 31 //Print the array. 32 public static void PrintArray(int[] array) 33 { 34 for (int i = 0; i < array.Length; i++) 35 { 36 Console.Write(array[i] + ", "); 37 38 } 39 Console.ReadLine(); 40 } 41 42 // Reverse an Array 43 public static void ReverseArray(int[] array, int left, int right) 44 { 45 46 for (; left < right; ++left, --right) 47 { 48 int tmp = array[left]; 49 array[left] = array[right]; 50 array[right] = tmp; 51 } 52 } 53 54 // Reverse thrice respectively. 55 public static void TransposeByIndex(int[] array, int index) 56 { 57 ReverseArray(array, 0, index); 58 ReverseArray(array, index + 1, array.Length - 1); 59 ReverseArray(array, 0, array.Length - 1); 60 } 61 62 //Transpose by value 63 public static void TransposeByValue(int[] array, int value) 64 { 65 for (int i = 0; i < array.Length; i++) 66 if (array[i] == value) 67 { 68 TransposeByIndex(array, i); 69 } 70 } 71 72 //Tanspose by segment 73 public static void TransposeBySegment(int[] array, int StartIndex, int Length) 74 { 75 int div = StartIndex + Length - 1; 76 int end = array.Length - 1; 77 ReverseArray(array, StartIndex, div); 78 ReverseArray(array, div + 1, end); 79 ReverseArray(array, StartIndex, end); 80 } 81 82 //Romove duplicated Elements 83 public static void RemoveDuplicated(int[] array) 84 { 85 for (int i = array.Length - 1; i > 0; i--) 86 { 87 for (int j = 0; j < i; j++) 88 { 89 if (array[i] == array[j]) 90 { 91 array[i] = 0; 92 } 93 } 94 95 } 96 97 for (int i = 0; i < array.Length - 1; i++) 98 { 99 for (int j = array.Length - 1; j > i; j--) 100 { 101 if (array[i] == 0 && array[j] != 0) 102 { 103 ReverseArray(array, i, j); 104 ReverseArray(array, i, j - 1); 105 } 106 } 107 } 108 109 110 } 111 } 112 }