집 > 기사 > Java > Java 어레이 고주파 테스트 포인트 예시 분석

Java 어레이 고주파 테스트 포인트 예시 분석

王林앞으로: 2023-04-29 21:52:05925검색

1. 배열 이론의 기본

배열은 연속적인 메모리 공간에 저장된 동일한 유형의 데이터 모음입니다. 첨자 아래에 해당하는 데이터는 첨자 인덱싱을 통해 얻을 수 있습니다.

예를 들어(문자 배열)~

Java 어레이 고주파 테스트 포인트 예시 분석

다음을 볼 수 있습니다.

1. 배열의 첨자는 0

2부터 시작합니다. 따라서 요소를 삭제할 때 배열의 주소는 연속입니다. , 덮어쓰기로만 수행할 수 있습니다.

예를 들어 인덱스가 2~인 요소를 삭제하려면 삭제할 요소를 덮어서 2 이후의 요소를 순서대로 이전 요소로 이동해야 합니다.

Java 어레이 고주파 테스트 포인트 예시 분석

Java 어레이 고주파 테스트 포인트 예시 분석 그래서 요소를 삭제해도 요소의 공백이 해제되지 않고 다음 요소가 앞으로 이동하여 삭제할 요소를 덮은 다음 배열 길이에서 1을 뺍니다. , 겉보기에 새로운 배열을 얻게 될 것입니다.

Java에서 2차원 배열의 저장 방식은 다음과 같습니다.

Java 어레이 고주파 테스트 포인트 예시 분석 2. 공통 테스트 포인트

1. 이진 검색

질문 링크: 이진 검색

이 질문의 전제는 다음과 같습니다. 반복되는 요소가 있으면 이진 검색 방법으로 반환된 요소 첨자가 고유하지 않을 수 있으므로 이는 이진 검색 방법을 사용하기 위한 전제 조건입니다.

이진 검색의 개념은 다음과 같습니다.

배열이 정렬되어 있다는 전제(오름차순 가정)에서 배열 중간의 값이 찾으려는 값보다 크면 찾을 요소는 다음과 같습니다. 후반부에 있는 값이 모두 중간값보다 크므로 1차 비교를 통해 범위를 절반으로 줄일 수 있으므로 후반부에 있을 수 없습니다. 이는 나중에도 동일하게 적용됩니다. 즉, 시간 복잡도가 줄어듭니다. O(logN)으로 변환하여 효율성이 크게 향상됩니다. 요소를 찾는 시간 복잡도가 O(logN)인 경우 먼저 두 개로 나눌 수 있는지 생각해 보세요.

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}

2. 요소 제거

몇몇 학생들은 "그냥 중복된 요소만 삭제하면 안 되지?"라고 말했을 수도 있습니다. 그러나 배열의 요소는 메모리 주소에서 연속적이라는 점을 알아야 합니다. 배열의 요소를 개별적으로 삭제할 수는 없으며 덮어쓸 수만 있습니다.

예: 배열과 val 값을 주었는데 배열에서 val 값과 동일한 요소를 삭제하라는 메시지가 표시됩니다.

아이디어 1: 잔인한 방법

두 개의 for 루프를 사용할 수 있습니다. val 값과 동일한 요소를 탐색할 때 삭제할 요소를 덮기 위해 다음 요소 전체를 앞으로 이동하지만 이 접근 방식은 확실히 시간이 많이 걸립니다. 복잡성이 너무 높습니다.

class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size;i++ ) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组后面集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--;
            }
        }
        return size;
    }
}

아이디어 2: 이중 포인터 방법

각각 느린 포인터와 느린 포인터를 가정하고 두 포인터가 삭제될 요소를 만나면 중지하고 삭제(덮어쓰기)를 기다립니다. ; 빠른 포인터가 왼쪽 요소에 도달하면 빠른 포인터의 요소를 느린 포인터에 할당한 다음 빠른 포인터가 전체 배열을 탐색할 때까지 두 포인터가 동시에 뒤로 이동합니다.

다음과 같이 이해될 수 있습니다. 0부터 시작하여 newLength 배열의 새 길이를 정의하고, 배열을 빠르게 탐색하는 빠른 포인터를 정의합니다. fast가 왼쪽 요소에 도달하면 해당 요소를 추가해야 함을 의미합니다. 새 배열(즉, newLength 첨자에 추가됩니다. 이는 newLength가 반환될 새 배열로 간주되기 전의 배열 부분과 동일하며, 이는 이 새 배열에 요소를 삽입하는 것과 동일합니다).

class Solution {
    public int removeElement(int[] nums, int val) {
        int fast = 0;// 定义一个快指针遍历数组
        int newLength = 0;// 定义新的数组长度
        while(fast < nums.length){
            if(nums[fast] != val){
                nums[newLength++] = nums[fast];
            }
            fast++;
        }
        return newLength;
    }
}

Java 어레이 고주파 테스트 포인트 예시 분석

1. 배열 이론의 기본

1. 이진 검색

질문 링크: 이진 검색

관련 기사