열심히 생각하는 공간

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Binary Search로 풀었으나. .  시간초과...ㅠㅠ 범위로 애 먹었다.

참고 코드

public class No34 {
    public static int[] searchRange(int[] nums, int target) {

        int start = 0, end = nums.length - 1;
        int[] result = {-1, -1};
        if(nums.length==0) {
            return result;
        }
        while (nums[start] < nums[end]) {
            int mid = start + (end - start)/2;
            if (nums[mid] > target) {
                end = mid - 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                if(nums[start] == nums[mid]) {
                    end--;

                } else {
                    start++;

                }
            }
        }
        if(nums[start]==nums[end] && nums[start]==target) {
            result[0] = start;
            result[1] = end;
        }
        return result;

        }

    }

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted

처음에 for문으로 풀었다가 속도가 너무 낮게 나오길래 어떤 유저의 Binary Search 방법을 찾아 공부했다.

진짜 풀수록 다양한 아이디어를 갖고있는 사람들이 많다.

 public int[] twoSum(int[] numbers, int target) {

        int start = 0, end = (numbers.length-1);

        if(numbers == null || numbers.length < 2) {
            return new int[]{};
        }
        while(start < end) {
            if(numbers[start] + numbers[end] == target) {
                return new int[]{start+1, end+1};
            } else if (numbers[start] + numbers[end] > target) {end--;}
            else start++;
        }

        return  new int[]{};



    }

공부한 사람의 원 코드는 이곳

하루에 두문제 이상씩 풀고 싶은데~~~ 항상 생각지 못한곳에서 막힌다.

1. 젤 첫번째로 범위 설정하기

2. while문으로 푸는 법 고민해보기

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.

Two Pointers 알고리즘으로 저번주부터 내리 풀었던 코드 유형이다. 다만, 첫 단추부터 느린 코드를 작성해서 그런지 계속 비슷한 아이디어로 문제를 해결하는 습관을 들인 것 같다..

public void moveZeroes(int[] nums) {
        ArrayList<Integer> arrList = new ArrayList<Integer>();

        for(int i=0; i<nums.length; i++) {
             if(nums[i] != 0) {
                arrList.add(nums[i]);
            }
        }
        for(int i=0; i<nums.length; i++) {
            if(i<arrList.toArray().length) {
                nums[i] = arrList.get(i);
            } else {
                nums[i] = 0;
            }
        }
    }

Description에서 SnowBall로 비유해서 만든 알고리즘이 있는데 진짜 신박하다.

https://leetcode.com/problems/move-zeroes/discuss/172432/THE-EASIEST-but-UNUSUAL-snowball-JAVA-solution-BEATS-100-(O(n))-%2B-clear-explanation 

Given an array, rotate the array to the right by k steps, where k is non-negative.
https://leetcode.com/problems/rotate-array/

쉽다고 생각하고 풀었는데 은근 시간이 많이 걸렸다. 범위에 대해 경우의 수를 생각해 봐야할 것.

다음 문제부턴 while문으로 푸는 법을 생각해 보자.

public void rotate(int[] nums, int k) {

        if(nums == null || nums.length == 0){
            return;
        }
        
        int[] result = new int[nums.length];
        k = k % nums.length;

        for(int i=0; i<nums.length; i++) {
            if(i<k) {
                result[i] = nums[nums.length-k+i];
            }else {
                result[i] = nums[i-k];
            }
        }
        
        for(int i=0; i<nums.length; i++) {
            nums[i]= result[i];      
        }
    }

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

https://leetcode.com/problems/squares-of-a-sorted-array/

정렬되지 않은 배열을 오름차순으로 배열하는 것. 문제는 해결됐으나 엄청 오래걸리고 그다지 좋은 풀이방식은 아닌 것 같다.

    public static int[] sortedSquares(int[] nums) {
        int[] output = new int[nums.length];
        int temp = 0;

        for(int i=0; i<nums.length; i++) {
            output[i] = nums[i] * nums[i];
        }

        for(int i=0; i<output.length-1; i++) {

            for(int j=i; j<output.length; j++) {
                if(output[i] > output[j]) {
                    temp = output[i];
                    output[i] = output[j];
                    output[j] = temp;

                }
            }

        }
        return output;

    }

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

https://leetcode.com/problems/search-insert-position/

Binary Search의 세 번째 문제이다. mid 값을 정해줄 때 overflow 발생하지 않게 해주는 것이 생각나서 이 문제에도 적용하였다.

nums 배열에 없는 target이 input값으로 넘어왔을 때 처리해 주는 부분이 시간을 많이 잡아먹은 것 같다.

public class No35 {

        public int searchInsert(int[] nums, int target) {
            int start = 0;
            int end = nums.length-1;
            int mid = 0;

            while(start <= end) {
                mid = start + (end-start) / 2;
                if (nums[mid] == target) {
                    return mid;
                } else if (nums[mid] > target) {
                    end = mid-1;
                } else if (nums[mid] <target) {
                    start = mid+1;
                }
            }
            return start;
        }

}

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

https://leetcode.com/problems/first-bad-version/

Binary Search로 풀면 되네 싶어서 쉽다고 생각했는데 Overflow랑 중간에 API를 활용하는 걸 아예 생각 안하고 있었더니 시간을 다 잡아먹었다. 계산할때 Overflow의 가능성을 염두해야겠다.

public class No278 {
    /* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

    public class Solution extends VersionControl {
        public int firstBadVersion(int n) {
            int start = 1;
            int end = n;
            while(start < end) {
                int mid = start + (end-start) / 2;
                // int mid = (start+end)/ 2;
                if(isBadVersion(mid)){
                    end = mid;
                } else {
                    start = mid+1;
                }
            }
            return start;
        }
    }
}

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.

(2) Binary Search - LeetCode

이진 탐색이란 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) 

인덱스 위치를 반씩 쪼개면서 정답을 찾아가는 방식이다. 예제 코드도 위키에 친절히 나와있어 응용했더니 풀렸다. 

알고보면 쉬운 문제인데 겁먹지 말아야 겠다.