leetcode658_k 개의 가장 가 까 운 요 소 를 찾 습 니 다.

1894 단어 알고리즘
정렬 된 배열, 두 개의 정수 k 와 x 를 지정 하고 배열 에서 x (두 수의 차이 가 가장 작은) 에 가장 가 까 운 k 개 수 를 찾 습 니 다.돌아 온 결 과 는 반드시 오름차 순 으로 배열 되 어야 한다.만약 두 개의 수가 x 의 차이 와 같다 면, 수치 가 비교적 작은 그 수 를 우선 선택한다.
예시 1:
입력: [1, 2, 3, 4, 5], k = 4, x = 3 출력: [1, 2, 3, 4] 
예시 2:
입력: [1, 2, 3, 4, 5], k = 4, x = - 1 출력: [1, 2, 3, 4] 
설명:
k 의 값 은 양수 이 고 주어진 정렬 배열 의 길이 보다 작 습 니 다.배열 이 비어 있 지 않 고 길이 가 10 ^ 4 배열 의 모든 요소 와 x 의 절대 치 는 10 ^ 4 를 초과 하지 않 습 니 다.
 
생각:
배열 이 질서 가 있 기 때문에 마지막 으로 찾 은 k 개의 요소 도 질서 가 있 을 것 입 니 다. 사실은 길이 가 k 인 하위 배열 을 되 돌려 주 었 습 니 다. 길이 가 n 인 배열 에서 n - k 개의 숫자 를 제거 하 는 것 과 같 습 니 다. 그리고 지 우 는 순 서 는 반드시 양쪽 에서 시작 하 는 것 이다. 왜냐하면 x 에서 가장 먼 숫자 는 반드시 수미 에 나타 날 것 이기 때문이다.매번 앞 뒤 두 숫자 와 x 의 거 리 를 비교 할 때마다 거리 가 큰 숫자 를 삭제 하고 나머지 배열 의 길이 가 k 일 때 까지 삭제 합 니 다.
//                        k
	 public List findClosestElements1(int[] arr, int k, int x) {
			 List res=new ArrayList<>();
			 int len=arr.length;
			 int left=0;
			 int right=len-1;
			 while (len>k) {
				if (Math.abs(arr[left]-x)>Math.abs(arr[right]-x)) {
					left++;
				}else {
					right--;
				}
				len--;
			}
	        for (int index = left; index <=right; index++) {
	                  res.add(arr[index]);       
			}
		     return res;	        
	    }

 
2 점 짜 리 방법 도 이용 할 수 있어 요.  가장 가 까 운 구간 의 출발점 을 찾다.
 public List findClosestElements(int[] arr, int k, int x) {
	        List res = new ArrayList<>();
	        int start = 0, end = arr.length-k;  //    k    end n-k
	        while(startMath.abs(arr[mid+k]-x)){ //     x             
	                start = mid+1;
	            } else {
	                end = mid;
	            }
	        }
	        for(int i=start; i

좋은 웹페이지 즐겨찾기