LeetCode Day1 Array Part1
Tags: leetcode, java, algorithms
Published: 2024-06-05 15:25:18

# Day  1 Array Part1

## LeetCode 704 Binary Search 

Some ideas are learned from [website](https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF)

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](https://leetcode.com/problems/binary-search/)


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 <sup>1</sup>/ <sub>2</sub> - 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.)



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ksb91xu39ijc9uqxj538.png)




```
    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](https://leetcode.com/problems/remove-element/description/)

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!