[알고리즘 학습] 2 차원 배열 의 찾기

문제 설명: 2 차원 배열 에서 찾 습 니 다.2 차원 배열 에서 모든 줄 은 왼쪽 에서 오른쪽으로 증가 하 는 순서에 따라 정렬 되 고 모든 열 은 위 에서 아래로 증가 하 는 순서에 따라 정렬 된다.함 수 를 완성 하 십시오. 이 2 차원 배열 과 정 수 를 입력 하여 배열 에 이 정수 가 포함 되 어 있 는 지 판단 하 십시오.예 를 들 어 {1, 2, 3, 4} {2, 4, 6, 7} {4, 5, 7, 8} {6, 7, 8, 9}}
해법 과 분석: 이분법 으로 찾 을 수 있 습 니 다.1. 네 개의 뿔 에서 출발점 을 찾 아 열 로 가 는 것 이 증가 & 걸 어 가 는 것 이 감소 하거나 열 로 가 는 것 이 감소 & 걸 어 가 는 것 이 증가 합 니 다.이 조건 에 맞 는 것 은 왼쪽 아래 와 오른쪽 상단 뿐이다.2. 왼쪽 아래 를 예 로 들 어 두 개의 지침 을 정의 하고 하 나 는 위로 가 고 하 나 는 오른쪽으로 간다 (증가).3. 어떻게 가요?현재 두 포인터 가 가리 키 는 2 차원 배열 의 값 이 검색 값 보다 큰 지 작은 지 판단 합 니 다. 검색 값 보다 크 면 위로, 검색 값 보다 작 으 면 오른쪽으로 갑 니 다.두 바늘 다 멈 추고 못 갈 때 까지.
참조 코드 는 다음 과 같 습 니 다.
/** *   。               。(             ,                ) * @param nums      * @param target      * @param column     * @param row      * @return */
public static boolean findNum(int[][] nums,int target,int column,int row)
{
    if(nums==null)
    {//    null  
        return false;
    }
    while (column>0&&row>0)
    {
        int current=nums[row-1][column-1]; //   

        if(current>target)
        {//      ,  (      ,           )
            --row;
        }
        else if(current<target)
        {//      ,  (      ,           )
            ++column;
        }
        else
        {//    
            return true;
        }
    }

    return false;
}
  • 첨부: 원본 주소
  • 좋은 웹페이지 즐겨찾기