배열 관련 알고리즘 문제

글 목록

가장 작은 k 개 찾기

배열 에서 중복 되 는 숫자

곱 하기 배열 구축

과 S 의 두 수

패 리 티 에 따라 배열

연속 서브 배열 의 최대 화

배열 을 가장 작은 수로 배열

과 S 의 연속 정수 서열

배열 에 한 번 밖 에 나타 나 지 않 는 숫자

최소 k 개 찾기
n 개의 정 수 를 입력 하고 가장 작은 k 개 를 출력 합 니 다.
생각:

빠 른 배열 의 사상 을 이용 하여 k 번 째 위치 에서 정확 한 수 를 찾 습 니 다. k 위치 앞의 수 는 k 위치 보다 작은 배열 이 고 k 뒤의 수 는 k 위치 요소 보다 큰 배열 입 니 다.

더미 정렬 을 이용 하여 대량의 데이터 에서 가장 크 거나 가장 작은 k 개의 숫자 를 찾 는 데 특히 적합 하 다.즉, 큰 용 기 를 구축 하고 크기 를 k 로 초기 화 하 며 변수 초기 수 입 니 다. 예 를 들 어 초기 배열 의 크기 가 k 보다 작 으 면 직접 돌아 갑 니 다. k 보다 크 면 배열 의 앞 k 개 요 소 를 선택 하여 더 미 를 채 운 다음 에 최대 로 조정 합 니 다.조정 이 끝 난 후에 초기 배열 에서 원 소 를 계속 꺼 냅 니 다. 만약 에 이 요소 가 쌓 인 지붕 보다 작 으 면 쌓 인 지붕 을 교체 하고 최대 더미 로 계속 조정 합 니 다. 만약 에 쌓 인 지붕 보다 크 면 바로 버 리 고 조정 하지 않 습 니 다.

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (input==null||input.length==0||input.length<k||k<=0) {
            return res;
        }
        int start  = 0;
        int end = input.length-1;
        int index = partition(input, start, end);
        //         k       。
        while (index != k - 1) {
            if (index > k - 1) {
                end = index-1;
                index = partition(input, start, end);
            } else {
                start = index+1;
                index = partition(input, start, end);
            }
        }
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }

   static int partition(int input[], int start, int end) {
        int tmp = input[start];
        while (start < end) {
            while (start < end && input[end] >= tmp) {
                end--;
            }
            input[start] = input[end];
            while (start < end && tmp >= input[start]) {
                start++;
            }
            input[end] = input[start];
        }
        input[start] = tmp;
        return start;
    }

배열 에서 중복 되 는 숫자
길이 가 n 인 배열 의 모든 숫자 는 0 에서 n - 1 의 범위 안에 있다.배열 의 일부 숫자 는 중복 되 지만 몇 개의 숫자 가 중복 되 는 지 모른다.숫자 마다 몇 번 씩 반복 되 는 지 모 르 겠 어 요.배열 에서 중복 되 는 숫자 를 찾 아 보 세 요.
생각:

배열 의 숫자 는 0 에서 n - 1 의 범위 내 이다.이 배열 에 중복 되 는 숫자 가 없다 면 대응 하 는 i 위치 데이터 도 i

입 니 다.

추가 공간 을 사용 하여 i 위치 수가 추가 공간 에 존재 하 는 지 판단 한다

public Integer duplicate(int[] numbers) {
    if(numbers.length = 0 || numbers == null) return -1;
    int length = numbers.length;
    ArrayList list = new ArrayList();
    for(int i = 0;i<length;i++){
        if(list.contains(numbers[i]) return numbers[i]
        else list.add(numbers[i]);
    }
    return -1;
}

곱셈 배열 구축
배열 A [0, 1,..., n - 1] 을 지정 하고 배열 B [0, 1, n - 1] 을 구축 하 십시오. 그 중에서 B 중의 요소 B [i] = A [0] A [1]... * A [i - 1] A [i + 1]... * A [n - 1].나눗셈 을 사용 할 수 없습니다.
사고방식: 행렬 의 방식 으로 먼저 왼쪽 아래 삼각형 을 계산 한 다음 에 오른쪽 위 삼각형 을 계산한다.그림 에 근거 하여 분석 하면 된다.

public class MultiArray {
	//        B，  A  i         ，
	//  A  i               O(n)
    public int[] multiply(int[] A) {
    	//  B   A[0] *...* A[i-1] A[n-1]*...*A[i+1]    
    	if(A == null || A.length ==0)
        	return A;
        int length = A.length;
        int [] B = new int[length];
        B[0] = 1;
        //         ，  B[0]      ，  1，
     	// B[0]   A[0]
        for (int i = 1; i < length; i++) {
			B[i] = B[i-1]*A[i-1];
		}
        int tmp =1;
        //       
        for (int i = length -1; i >=0; i--) {
			//   B[i]            
        	B[i] *=tmp;
		tmp *= A[i];
		}
        
        return B;
    }
}

S 의 두 수
정수 배열 nums 와 목표 값 target 을 지정 합 니 다. 이 배열 에서 목표 값 의 두 정 수 를 찾 아 배열 아래 표 시 를 되 돌려 주 십시오.

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

패 리 티 에 따라 배열 을 정렬 하 다.
마이너스 정수 가 아 닌 배열 A 를 지정 하고 A 의 모든 짝수 요소 로 구 성 된 배열 을 되 돌려 줍 니 다. 그 다음 에 A 와 의 모든 홀수 요 소 를 되 돌려 줍 니 다.

public int[] sortArrayByParity(int[] A) {
    int lo = 0;
    int hi = A.length -1;
    while(lo < hi){
        while(A[lo] % 2 == 0){
            if(lo == hi) break;
            lo++;
        } 
        while(A[hi] % 2 != 0){
            if(hi == lo) break;
            hi--;
        }
        if(lo > hi) break;
        int temp = A[lo];
        A[lo] = A[hi];
        A[hi] = temp;
    }    
}

연속 하위 배열 의 최대 합
알고리즘 시간 복잡 도 O (n) 는 totalk 로 누적 치 를 기록 하고 max Sum 기록 과 최대 사상 을 바탕 으로 합 니 다. 한 개의 숫자 A 에 대해 A 의 왼쪽 누적 수가 마이너스 가 아니라면 A 를 더 하면 수치 가 A 보다 작 지 않 고 누적 치가 전체 와 기여 하 는 것 이 라 고 생각 합 니 다.앞의 몇 가지 누적 치 마이너스 라면 전체 에 해롭다 고 생각 하고 totalk 은 현재 값 을 기록 합 니 다.이때 max Sum 보다 크 면 max Sum 으로 기록 합 니 다.

public class Solution {
	public int FindGreatestSumOfSubArray(int[] array) {  
		if(array.length == 0)
			return 0;
		int total = array[0];//         
		int maxsum = array[0];//        
		for (int i = 1; i < array.length; i++) {
			if(total >= 0)
				total = total + array[i];
			else
				total = array[i];
			if(total > maxsum)
				maxsum = total;
		}
		return maxsum;
	}
}

배열 을 가장 작은 수로 배열 하 다.
정수 배열 을 입력 하고 배열 의 모든 숫자 를 연결 하여 하나의 숫자 로 배열 하 며 연결 할 수 있 는 모든 숫자 중 가장 작은 숫자 를 인쇄 합 니 다.예 를 들 어 배열 {3, 32, 321} 을 입력 하면 이 세 숫자 가 배열 할 수 있 는 최소 숫자 는 321323 이다.
문제 풀이 방향: 대수 문 제 를 고려 하여 전체 배열 을 String 배열 로 바 꾼 다음 에 String 배열 을 정렬 하고 마지막 으로 정렬 된 문자열 배열 을 연결 합 니 다.관건 은 정렬 규칙 을 만 드 는 것 이다.정렬 규칙 은 다음 과 같 습 니 다. ab > ba 는 a > b 이 고 ab < ba 는 a < b 이 며 ab = ba 는 a = b 입 니 다.예 를 들 어 '3', '31' 이지 만 '331', '313' 이 므 로 이들 을 연결 하여 비교 해 야 한다.

public String PrintMinNumber(int [] numbers) {
    if(numbers == null || numbers.length == 0)
        return "";
    int len = numbers.length;
    String[] str = new String[len];
    StringBuffer sb = new StringBuffer();
    //             。
    for (int i = 0; i < len; i++) {
	    str[i] = String.valueOf(numbers[i]);
	}
    //          str      
    Arrays.sort(str, new Comparator<String>() {
		@Override
		public int compare(String s1, String s2) {
			String c1 = s1 + s2;
			String c2 = s2 + s1;
			return c1.compareTo(c2);
		}
 
	});
    //       ，       stringbuffer    
    for (int i = 0; i < len; i++) {
		sb.append(str[i]);
	}       
    return sb.toString();
}

S 와 의 연속 정수 시퀀스

n = 2k + 1 시 n 항 연속 정수 서열 의 합 이 S 인 조건: n & 1 & & S / n = 0 해석 논리 와 왼쪽 요구 n 은 홀수 이 고 오른쪽 은 전체 서열 의 평균 수 를 중간 수 로 요구한다.

n = 2k 시 n 항 연속 정수 서열 의 합 이 S 인 조건: S% n * 2 = = n 이 S% n 을 해석 한 결 과 는 중간 두 개의 왼쪽 에 있 는 것 이 고 곱 하기 2 는 바로 항 수 였 다.예 를 들 어 기 존 S = 39, 6 개의 연속 정수 서열 과 식 은 S 일 수 있 습 니까?공식 을 적용 하면 39% 6 * 2 = 6 = 6 이다. 우리 도 알다 시 피 이번 서열 은 4, 5, 6, 7, 8, 9 이 고 나머지 결 과 는 3 으로 대응 하 는 값 이 6 인 항목, 즉 중간 항목 왼쪽 의 항목 이다.

과 S, 항 수 는 n 인 데 이 서열 을 어떻게 씁 니까?S / n - (n - 1) / 2 판독 에 따 른 나눗셈 은 바닥 나눗셈 (floor) 으로 최종 결과 가 있 든 없 든 그대로 버린다.상기 예 를 사용 하면 39 / 6 = 6, 6 은 마침 중간 항목 왼쪽 의 그 항목 이 고 6 - (6 - 1) / 2 = 4 는 마침 서열 의 가장 왼쪽 이다.서열 을 쓰 면 문제 가 없다.

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
 
        vector<vector<int> > allRes;
        for (int n = sqrt(2 * sum); n >= 2; --n) {
            if (((n & 1) == 1 && sum % n == 0) || (sum % n * 2 == n)){
                vector<int> res;
                //j    ，k      
                for(int j = 0,k = sum / n - (n - 1) / 2; j < n; j++, k++)
                    res.push_back(k);
                allRes.push_back(res);
            }  
        }
        return allRes;
    }
};

그리고 주의해 야 할 것 은 S = (a0 + a0 + n - 1) * n / 2, 등차 서열 공식 은 당연히 말 할 필요 가 없다.이 를 축소 하면 S > n 제곱 / 2 가 있 습 니 다.즉 n < 근호 2S (이 점 은 해법 4 에서 도 언급 됨).이렇게 하면 옮 겨 다 니 는 횟수 를 줄 일 수 있다.for 순환 에 나타 납 니 다.

for (int n = sqrt(2 * sum); n >= 2; --n)

시간 복잡 도 는 O (루트 sum) 입 니 다.
배열 에 한 번 만 나타 나 는 숫자.
하나의 정형 배열 에 두 개의 숫자 를 제외 하고 다른 숫자 는 모두 두 번 나 타 났 다.프로그램 을 써 서 이 두 개의 한 번 만 나 오 는 숫자 를 찾 아 보 세 요.