Coding Exercise – Remove Element – C++ – Online Judge


Question: Given an array and a element, remove all instances of that value in place and return the new length.

The order of elements can be changed and it doesn’t matter what you leave beyond the new length.

Original Problem Pagehttp://oj.leetcode.com/problems/remove-element/

There are two important hints: (1) the order of elements can be changed, meaning that we can swap elements for our conveniences. (2) it doesn’t matter what we leave beyond the new length, meaning that we don’t need to care the values (don’t need to preserve their original values even we don’t need it)

Could someone think of a shorter solution than this?

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        for (int i = 0; i < n; i ++) {
            while ((A[i] == elem) && (i < n) && (n > 0)) {
                A[i] = A[n-- - 1]; // swap current with the end and n--
            }
        }
        return n;
    }
};
class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        for (int i = 0; i < n; i ++) {
            while ((A[i] == elem) && (i < n) && (n > 0)) {
                A[i] = A[n-- - 1]; // swap current with the end and n--
            }
        }
        return n;
    }
};

Check each position, and swap it (not actually) with the current end, so the element at the end jumps to the current position and overwrites its value (it is lost, but we don’t care). Remember to decrement the length with n–.

Again, this is done in place (no additional space is required). We have a while loop to check if the value at the end is still to be removed, so we can continue removing them until it is not. It looks like tex_8fb1f5024a605dc7737c61a8a376e067 Coding Exercise - Remove Element - C++ - Online Judge algorithms beginner c / c++ data structure implementation interview questions programming languages tricks But in fact, it is practically tex_caa5d58969fcc95bcd6477b6782501fa Coding Exercise - Remove Element - C++ - Online Judge algorithms beginner c / c++ data structure implementation interview questions programming languages tricks complexity, do you know why? 🙂

EOF–

GD Star Rating
loading...
385 words
Last Post: Coding Exercise - Remove Duplicates From Sorted List - C++ - Online Judge
Next Post: How to Perform Case-insensitive Valid Palindrome AlphaNum String Check?

The Permanent URL is: Coding Exercise – Remove Element – C++ – Online Judge

Leave a Reply