LeetCode: Remove Element

14104 ワード
テキストリンク

Question

  • https://leetcode.com/problems/remove-element
  • Level: Easy
  • Type: Binary Search or some kind of implementation

    • Core Logic


    Intuitive Logic

  • Intuitively, we can use iterate through vector, and remove corresponding elements
  • Which 'Looks like' O(N) solution, but if we look at the vector.erase() 's time complexity, worst case would take O(N) for each single erase operation.
  • Meaning, looping through vector takes O(N), and if we remove an element, that operation also takes O(N).
  • So in worst case[i.e vector with all 2's and removeTarget = 2], this Logic takes O(N^2) times.

    • Bit more optimized Logic && Algorithm

  • This approach will try to make logic's time complexity to O(N*Log(N))
  • First, sort array with ascending-order.
  • This takes O(N*Log(N)) in worst case.
  • Use binary search to search target.[O(Log(N))]
  • If there are multiple targets, find range in this case.
  • Remove Target Range
  • Worst case would be O(N)
  • Done!

    • Code

    class Solution {
public:
    
    void getStartRange(int& container, int middleIndex, int& target, vector<int>& nums) {
        container = -1;
        
        while (middleIndex >= 0) {
            if (nums[middleIndex] != target) {
                container = middleIndex+1;
                break;
            }
            middleIndex--;
        }
        
        if (container == -1) container = 0;
    }
    
    void getEndRange(int& container, int middleIndex, int& target, vector<int>& nums) {
        container = -1;
        
        while (middleIndex < nums.size()) {
            if (nums[middleIndex] != target) {
                container = middleIndex-1;
                break;
            }
            middleIndex++;
        }
        
        if (container == -1) container = nums.size()-1;
    }
    
    int removeElement(vector<int>& nums, int val) {
        if (nums.empty()) {
            return 0;
        }
        sort(nums.begin(), nums.end());
        
        int start = 0;
        int end = nums.size()-1;
        int middleIndex = (start + end) / 2;
        
        int eraseStart = -1;
        int eraseEnd = -1;
        
        while (start <= end) {
            middleIndex = (start + end) / 2;
            if (nums[middleIndex] < val) {
                // Right
                start = middleIndex+1;
            } else if (nums[middleIndex] > val) {
                // Left
                end = middleIndex-1;
            } else {
                // Same
                getStartRange(eraseStart, middleIndex, val, nums);
                getEndRange(eraseEnd, middleIndex, val, nums);
                break;
            }
        }
        
        if (eraseStart != -1 && eraseEnd != -1) {
            nums.erase(nums.begin()+eraseStart, nums.begin()+eraseEnd+1);
        }
        
        return nums.size();
    }
};

    Submission



    [BOJ 2146]ブリッジ(Java)
    [BOJ]1186節最も価値のあるヒップホップjava