[LeetCode]238. 자신이 아닌 배열의 곱을 해결하기 위한 아이디어

Question

길이가 n인 정수 배열 nums가 주어지면(여기서 n > 1) 출력 배열 출력을 반환합니다. 여기서 출력[i]는 nums[i]를 제외한 nums의 나머지 요소의 곱과 같습니다.

예:

입력: [1,2,3,4]
출력: [24,12,8,6]

Tips: 질문 데이터는 배열 접미사(또는 전체 배열)의 곱은 32비트 정수 범위 내에 있습니다.

지침: 제발나눗셈을 사용하지 말고 O(n) 시간 복잡도 내에서 이 문제를 완료하세요.

고급: 일정한 공간 복잡성 내에서 이 문제를 해결할 수 있습니까? (공간 복잡도 분석을 위해 출력 배열은 추가 공간으로 간주되지 않습니다.)

Solution

질문을 받았을 때 첫 번째 아이디어는 루프용 2개, 제품용 1개, 분할용 1개였습니다. 그러나 나중에 나눗셈을 사용하지 말라는 지시사항을 발견하고 다른 방법을 사용해야 했습니다.

우리는 우리 자신 이외의 누적 곱셈을 계산하므로 현재 위치를 분할점으로 사용하여 왼쪽 요소의 곱과 오른쪽 요소의 곱을 각각 계산한 다음 곱할 수 있습니다.

다음 솔루션이 있습니다.

알고리즘 1(LeetCode 공식 솔루션에서 추출):

두 개의 빈 배열 L과 R을 초기화합니다. 주어진 인덱스 i에 대해 L[i]는 i 왼쪽에 있는 모든 숫자의 곱을 나타내고, R[i]는 i 오른쪽에 있는 모든 숫자의 곱을 나타냅니다.

L 및 R 배열의 값을 채우려면 두 개의 루프를 사용해야 합니다. 배열 L의 경우 첫 번째 요소 왼쪽에 요소가 없으므로 L[0]은 1이어야 합니다. 다른 요소의 경우: L[i] = L[i-1] * nums[i-1].

마찬가지로 배열 R의 경우 R[length-1] 은 1이어야 합니다. 길이는 입력 배열의 크기를 나타냅니다. 기타 요소: R[i] = R[i+1] * nums[i+1].

R 및 L 배열이 채워지면 입력 배열을 반복하기만 하면 되며 인덱스 i의 값은 L[i] * R[i]입니다.

class Solution {
    public int[] productExceptSelf(int[] nums) {
  int arrLen = nums.length;
  int[] leftNums = new int[arrLen];
  int[] rightNums = new int[arrLen];
  leftNums[0] = 1;rightNums[arrLen-1] = 1;
  
  for(int i = 1; i < arrLen; i++){
   leftNums[i] = leftNums[i-1] * nums[i-1];
   rightNums[arrLen-i-1] = rightNums[arrLen-i] * nums[arrLen-i];
  }
  
  for(int i = 0; i < arrLen; i++){
   leftNums[i] *= rightNums[i];
  }
  
  return leftNums;
 }
}

복잡도 분석

시간 복잡도: O(N), 여기서 N은 배열 숫자의 크기를 나타냅니다. L 및 R 배열의 전처리와 최종 순회 계산은 모두 O(N) 시간 복잡도입니다.

공간 복잡성: O(N), 여기서 N은 배열 숫자의 크기를 나타냅니다. L 및 R 배열은 답을 구성하는 데 사용됩니다. L 및 R 배열의 길이는 배열 nums의 크기입니다.

알고리즘 2: 공유 배열 방법

전체 아이디어는 공식 문제 해결 아이디어인 왼쪽 곱셈 * 오른쪽 곱셈과 동일합니다.

반환 배열 returnNums 을 정의하고 이를 공유 배열로 처리하면서 왼쪽과 오른쪽 끝에서 데이터를 채운 다음 왼쪽과 오른쪽을 정의하여 왼쪽과 오른쪽 제품을 저장하고 루프에서 반복적으로 업데이트합니다.

1. 두 포인터가 만나기 전에 간단히 배열을 채우세요.

2. 두 포인터가 상호 작용할 때(홀수 길이에서만 발생) 채우기 값은 왼쪽*오른쪽입니다.

3. 둘이 만난 후 배열의 값은 최종 값으로 채워져야 합니다. 왜냐하면 왼쪽 부분에 왼쪽 제품이 저장되었고 오른쪽 제품이 계산되려고 하기 때문입니다. 오른쪽 부분에 보관되어 있고, 왼쪽 제품을 얻으려고 합니다. 그러니 그냥 직접 곱해보세요. returnNums[i] = 왼쪽 및 returnNums[j] = 오른쪽.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int arrLen = nums.length;
        int[] returnNums = new int[arrLen];
        int left = 1, right = 1;    // 临时存储
        returnNums[0] = 1; returnNums[arrLen-1] = 1;
        for(int i = 1, j = arrLen-2; i < arrLen; i++, j--){
            left *= nums[i-1];
            right *= nums[j+1];
            if(i < j){  // 两指针为交会
                returnNums[i] = left;
                returnNums[j] = right;
            }else if(i == j){   // 两指针重合，奇数位情况下发生
                returnNums[i] = left*right;
            }else{              // 两指针错位
                returnNums[i] *= left;
                returnNums[j] *= right;
            }
        }
        return returnNums;
    }
}

복잡성 분석

시간 복잡도: O(N), 이전 문제 해결 방법과 동일하게 길이 N의 루프가 수행되고, 시간 복잡도는 O(N ).

공간 복잡성: O(1) 제목에서 언급했듯이 반환된 배열의 공간은 계산되지 않으므로 사용되는 추가 저장 공간은 왼쪽과 오른쪽입니다. 따라서 일정한 수준의 공간 복잡도만 존재합니다.

위 내용은 [LeetCode]238. 자신이 아닌 배열의 곱을 해결하기 위한 아이디어의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!