기억하고싶은것들

Given an integer array nums,

move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

integer 배열 nums가 주어진다. 

0을 배열의 맨뒤로 옮겨라, 단 0이 아닌 배열의 숫자 순서는 유지해야 한다.

주의 : 주어진 배열을 그대로 사용해야 한다. 다른 배열을 선언해서는 안된다.

두 개의 포인터를 이용하여서 배열의 맨 앞을 가리키도록 하여

하나는 값이 0인 배열의 인덱스를 가리키고

다른 하나는 0이 아닌 배열의 인덱스를 찾아 서로 위치를 바꾸어주도록 문제를 풀어보자 

    public void moveZeroes(int[] nums) {
        int idx = 0; // 0을 가르키는 포인터

        for (int i = 0; i < nums.length; i++) { // 0이 아닌 값을 찾는 포인터 
            if (nums[i] != 0) {
                swap(nums, i, idx);
                idx++;
            }
        }
    }

만약 배열의 첫 인덱스가 0이 아닌 경우에는 아래 for문에서 0을 가리키는 idx의 값이 ++ 되므로 0을 찾을 때까지 

idx, i가 같이 ++된다. 

    private void swap(int[] nums, int i, int idx) {
        int tmp = nums[i];
        nums[i] = nums[idx];
        nums[idx] = tmp;
    }

문제출처 : 

https://leetcode.com/problems/move-zeroes/

Quick Sort는 배열을 기반으로 동작하기 때문에 배열에 대한 기본적인 설명을 한다.

Array (배열)

Random Access 가능 

Backtracking, Dynamic Programming과 같은 문제와 조합하여 많이 나옴

2차원, n차원 배열과 조합되는 문제 - graph

배열과 단골 조합 문제 - Sorting

Stable Sort - Merge Sort ( 정렬 후 조건이 같은 케이스는 순서가 변하지 않는다)

Unstable Sort - Quick Sort ( 정렬 후, 조건이 같은 케이스라도 순서가 변할 수 있다)

배열과 단골 조합문제 - Search 

정렬이 되어있지 않은 경우 O(n)

정렬이 되어있는 경우 - O(logn) (binary search) 

Quick Sort 

핵심 키워드 pivot, partitioning

하나의 리스트를 pivot을 기준으로 두 개의 부분 리스트로 나눈다.

부분 리스트 중에 하나는 pivot보다 작은 값들이 모여있는 리스트

다른 하나는 pivot보다 큰 값들이 모여있는 리스트로 구성된다.

각각의 부분 리스트에 대해서 다시 재귀적으로 위의 동작을 반복한다.

(분할 정복 - Divide and Conquer)

    private void quicksort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = partition(arr, left, right);

            quicksort(arr, left, pivot - 1);
            quicksort(arr, pivot + 1, right);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int low = left;
        int hight = right;

        int pivot = arr[left];

        while (low < hight) {
            while (arr[hight] > pivot && hight > low) {
                hight--;
            }

            while (arr[low] <= pivot && hight > low) {
                low++;
            }

            swap(hight, low, arr);
        }

        swap(left, low, arr);
        return low;
    }

    private void swap(int hight, int low, int[] arr) {
        int temp = arr[hight];
        arr[hight] = arr[low];
        arr[low] = temp;
    }

worst case - O(n*n)

best case - O(nlogn)

You are given two integer arrays nums1 and nums2, sorted in nondecreasing order,

and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, 

but instead be stored inside the array nums1. 

To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, 

and the last n elements are set to 0 and should be ignored. 

nums2 has a length of n.

두 개의 integer 오름차순 배열 nums1, nums2과 m, n integer를 받는다.

m, n은 각 배열이 가지고 있는 element의 개수이다.

이 두 배열을 하나의 오름차순 배열로 통합하여라.

단, 리턴되는 배열은 새로 정의된 배열이 아닌 nums1 배열이어야 한다.

nums1 배열은 크기가 m+n이다. 

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

정렬된 두 개의 배열을 merge 해야 한다.

단, 새로운 배열을 생성하여 merge 하는 것이 아닌 주어진 배열에서 merge가 이루어져야 한다.

주어진 배열의 마지막 element들을 point 하고 그중에 큰 값을 nums1 배열에 입력하는 형식으로 문제를 해결해 보자.

해당 순회를 마무리하는 조건으로는 각 배열의 pointer들이 0보다 작아진 경우이다. 

후에 만약 nums2의 pointer가 첫 index까지 순회를 하지 못한 경우에는 해당 값들을 nums1에 입력해주면 모든 배열을 순회한 것이다. 

    public void merge(int[] nums1, int m, int[] nums2, int n) {

        int nums1Idx = m - 1;
        int nums2Idx = n - 1;

        int point = nums1.length - 1;

        while (nums1Idx >= 0 && nums2Idx >= 0) {

            if (nums1[nums1Idx] >= nums2[nums2Idx]) {
                nums1[point] = nums1[nums1Idx];
                point--;
                nums1Idx--;
            } else {
                nums1[point] = nums2[nums2Idx];
                point--;
                nums2Idx--;
            }
        }

        if (nums2Idx >= 0) {
            while (nums2Idx >= 0) {
                nums1[point] = nums2[nums2Idx];
                point--;
                nums2Idx--;
            }
        }

    }

시간 복잡도는 각 배열을 모두 순회하므로 O( M + N )이다.

문제 출처

https://leetcode.com/problems/merge-sorted-array/

704. Binary Search

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.

오름차순으로 정렬된 integer 배열과 타깃 integer가 주어진 상황에서 

타깃을 배열에서 찾는 코드를 작성하여라

타깃이 존재한다면 해당 숫자가 들어있는 배열의 인덱스를 반환하고, 없다면 -1을 반환하라

반드시 시간 복잡도가 O(log n)인 알고리즘으로 작성하라

정렬된 배열에서 값을 찾는 문제로 시간 복잡도가 O(log n)인 알고리즘을 사용해야 한다. 

Binary Search를 이용하여 문제를 해결하도록 하자.

    public int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;
        int pivot = 0;

        while (left <= right) {
            pivot = (left + right) / 2;

            if (target == nums[pivot]) {
                return pivot;
            } else if (nums[pivot] < target) {
                left = pivot + 1;
            } else {
                right = pivot - 1;
            }
        }
        return -1;
        
    }

먼저 left, right 인덱스를 지정하고,

해당 인덱스들을 기반으로 while loop의 조건을 지정한다.

Binary Search의 경우에는 left 인덱스가 right 인덱스보다 큰 경우에는 타깃으로 하는 값이 없는 경우이므로 해당 조건이 while loop에 들어가게 된다. 

Binary Search에서는 각각의 left, right 인덱스의 중간값을 pivot으로 설정하고 

해당 값을 기준으로 다음 조건의 인덱스를 지정한다.

pivot 인덱스의 배열값이 타깃보다 작은 경우에는 left 인덱스를 pivot 다음 인덱스로 지정

pivot 인덱스의 배열값이 타깃보다 큰 경우에는 right 인덱스를 pivot 이전 인덱스로 지정

문제 출처

https://leetcode.com/problems/binary-search/