https://leetcode.com/problems/intersection-of-two-arrays/ Intersection of Two Arrays - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Given two arrays, write a function to compute their intersection. Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2] Example 2: Input: ..
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ Two Sum II - Input array is sorted - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target num..
https://leetcode.com/problems/binary-search/ Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1. Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 Example 2: Input: nums = [-1,0,3,5,9,12], targe..
선형검색은 순차 검색이라고 불리기도 한다. 선형 검색은 데이터의 집합의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아낸다. 선형검색은 링크드리스트에서 자주 쓰이는 방법이다. 데이터를 정렬하거나 따로 건드릴 필요는 없으나, 데이터의 양이 많아지면 소요된느 시간도 비례해서 늘어나고, 하나씩 일일이 비교하여서 비효율적이라는 단점이있다. 1 2 3 4 5 6 7 8 9 10 public static int search(int arr[], int x) { int n = arr.length; for(int i = 0; i = l) { int mid = l + (r - l) / 2; if (arr[mid] == x) return mid; if (arr[mid] > x) return binarySearch..
시간 복잡도, 공간 복잡도에 관하여
파일을 다른 사람에게 보낸다고 할때 보낼수 있는 방법은 여러가지가 있다. 이메일을 통해서 온라인으로 보낼수도 있고 교통수단을 이용해서 물리적으로 직접 전달하는 방법도 있다. 파일크기가 작다면 당연히 온라인 전송으로 보내는게 옳은 방법이다. 하지만 파일크기가 엄청나게 크다면 어떨까? 교통수단을 통해 물리적으로 전달하는게 빠를수도 있을것이다. 이것을 바로 점근적 실행 시간(asymptotic runtime), 또는 big-O 시간에 대한 개념이다. 온라인 전송 : O(s) 여기서 s는 파일 크기이고 파일크기가 증가함에 따라 전달하는 시간 또 한 선형적으로 증가한다. 물리적 전달 : O(1) 파일크기에 상관없이 전달하는 시간은 항상 똑같다. 상수의 시간만큼 소요된다. Big-O : 시간의 상항을 나타낸다. 실..