LeetCode Day1 Array Part1

Day 1 Array Part1

LeetCode 704 Binary Search

Some ideas are learned from website

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Original Page

About runtime complexity O(log n), it seems like we have to consider the method that is about something half, so the binary search was adopted.

There some keyword we should to pay attention for:
array , O(log n) , sorted

-> Binary Search

binary means that if we want to search some target, we can systematically divide into two ¹/ ₂ - original-size arrays
e.g. length 6 -> one length3 + one length 2
(Here the total count decreases by 1 because we have already evaluated one of the numbers.)

    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1;

        while(left <= right){
            // We find the middle of left and right by using this way to avoid overflow
            // >> Bitwise operation can improve a little performance compared with normal division operations
            int mid  = left +((right - left) >> 1);

            // if we find the targe then return it 
            if(target == nums[mid]){
                return mid;
            } 
            // target larger than middle means that we have to find the right half array so we change left side 
            else if(target > nums[mid]){
                left = mid+1;
            }
            else {
                right = mid-1;
            }
        }
        return -1;
    }

Another key thing is that we should focus on

while(left <= right)

Also, we can use

while(left < right)

However, using this condition for evaluation may lead to slight differences in the subsequent content.

One of the biggest problems is that when the loop ends, at that moment left = right = middle and this number has not been evaluated, so we need an additional check for it.

        if (array[left] == target) {
            return left;
        }

So be careful when we set the loop condition!

LeetCode 27.Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.... etc.
Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.
Original Page

there are some keywords in this scenario:
in-place, array

The key method

we can us O(n) ways instead of O(n^2)

that means we can work by only using 1 loop

if we remove the target element in-place, the datastructure array can not remove element. According to the problem description, we simply move all instances of the target to the end of the array(the original array) and return the count of remaining elements.

And because we do not need to keep the order in this question.
We can use left and right vector\ to solve the problem
the left vetctor : evaluate the element
the right vector:

• recode the swaped data
• avoiding re-evaluating

    public int removeElement(int[] nums, int val) {

        int left = 0; 
        int right = nums.length-1;
        while(left <= right){
            if(nums[left] == val){
                nums[left] = nums[right--];
                continue;
            }
            left++;
        }
        return left;
    }

the key thing is that the index should be smaller than the number of these elements by 1 !!!
the index 0 means there is 1 elements!
so that when the loop ends, the left will be the number of the result elements.

We can also use fast and slow vector
in this scenario:
the fast vector: evaluate the element
the slow vector: save the non-target element and can be seen as a new\array even though we use it in-place.

    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
        // Here we find the non-target value
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slowIndex++;
            }
        }
        return slowIndex;
    }

The difference between them is

• left-right-vector method focuses on moving and swapping the target element and move them to the end
• fast-slow-vector method focuses on moving and assigning the non-target element to the front!