In C#, we may use the following method to Remove Null Elements from a List:
1 2 3 4 5 6 7 | static void RemoveNull<T>(List<T> list) { for (int i = list.Count - 1; i >= 0; i--) { if (list[i] == null) { list.RemoveAt(i); // O(n) } } } |
static void RemoveNull<T>(List<T> list) { for (int i = list.Count - 1; i >= 0; i--) { if (list[i] == null) { list.RemoveAt(i); // O(n) } } }
The overall complexity is O(N^2) as the RemoveAt in List is O(N). We can totally do this in O(N) by moving the non-empty elements forward and then delete the extra spaces.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | static void RemoveNull<T>(List<T> list) { // Find Fist Null Element in O(n) var count = list.Count; for (var i = 0; i < count; i++) { if (list[i] == null) { // Current Position int newCount = i++; // Copy non-empty elements to current position in O(n) for (; i < count; i++) { if (list[i] != null) { list[newCount ++] = list[i]; } } // Remove Extra Positions O(n) list.RemoveRange(newCount, count - newCount); break; } } } |
static void RemoveNull<T>(List<T> list) { // Find Fist Null Element in O(n) var count = list.Count; for (var i = 0; i < count; i++) { if (list[i] == null) { // Current Position int newCount = i++; // Copy non-empty elements to current position in O(n) for (; i < count; i++) { if (list[i] != null) { list[newCount ++] = list[i]; } } // Remove Extra Positions O(n) list.RemoveRange(newCount, count - newCount); break; } } }
The inner loop will break once the first Null element is found – despite there are two nested for loops, the overall complexity is O(N).
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
235 wordsloading...
Last Post: How to Clone Variables (The Clone Function) in Javascript?
Next Post: The Javascript's Memorization Function to Speed Up Recursion (Dynamic Programming)