496. Next Greater Element I

문제: nums 1 의 요소 가 nums 2 의 부분 집합 인 nums 1 과 nums 2 두 배열 (중복 되 지 않 음) 이 제 공 됩 니 다. nums 2 의 해당 장소 에서 nums 1 의 요소 에 대한 다음 더 큰 숫자 를 모두 찾 습 니 다.
The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.
문제 설명: 문 제 는 중복 요소 가 없 는 두 개의 배열 nums 1, nums 2 를 보 여 주 었 습 니 다. 그 중에서 nums 1 은 nums 2 의 하위 배열 입 니 다.길이 가 nums 1 과 같 고 nums 1 요소 에 대응 하 는 nums 2 요소 의 다음 큰 요소 로 구 성 된 배열 을 요구 합 니 다. 하위 배열 요소 보다 큰 경우 가 없 으 면 - 1 로 돌아 갑 니 다.
개인 문제 풀이 방향: 1. 요소 가 같은 배열 의 위 치 를 찾 습 니 다.2. 찾 으 려 는 요소 보다 큰 값 을 찾 습 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.처음에는 Array. sort (int [] nums) 와 Array. binary Search (int [] nums, int key) 를 사용 하여 정렬 과 검색 방법 으로 위치 추적 을 편리 하 게 하려 고 했 으 나 정렬 을 거 친 배열 을 무시 하고 요소 순서 가 바 뀌 었 습 니 다.

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

                for( int i = 0; i < nums1.length; ++i){
                    int j = 0;
                    for(;j < nums2.length; ++j){//        j，          ，     ，        。
                        if(nums2[j] == nums1[i])                            
                            break;//      

                    }
                    int exch = nums1[i];
                    nums1[i] = -1;

                    for(++j; j < nums2.length; ++j){
                        if(nums2[j] > exch){//      nums2[j] >nums2[j-1]    ，   j   。
                            nums1[i] = nums2[j];
                            break;
                        }
                    }
                }
                return nums1;
    }
}

운행 시간 은 14ms 로 운행 속도 가 비교적 느리다.
범례 해결 방법:

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if(nums1.length == 0) return new int[]{};
        int[] res = new int[nums1.length];
        int max = Integer.MIN_VALUE;
        for(int num : nums2){
            if(max < num) max = num;
        }
        int[] map = new int[max + 1];
        Arrays.fill(map, -1);
        for(int i = 0 ; i < nums2.length ; i ++){
            map[nums2[i]] = i;
        }
        for(int i = 0 ; i < nums1.length ; i ++){
            if(nums1[i] >= max) res[i] = -1;
            else{
                int index = map[nums1[i]];
                while(++index < nums2.length){
                    if(nums2[index] > nums1[i]){
                        res[i] = nums2[index];
                        break;
                    }
                }
                if(res[i] == 0) res[i] = -1;
            }
        }
        return res;
    }
}