차례
문제 설명
”Plus One”문제에서 배열의 각 요소가 숫자의 숫자를 나타내는 배열이 제공됩니다. 완전한 배열은 숫자를 나타냅니다. XNUMX 번째 인덱스는 MSB 번호의. 숫자에 선행 XNUMX이 없다고 가정 할 수 있습니다.
우리의 임무는 주어진 숫자에 XNUMX을 더한 다음 결과를 배열 형태로 반환하는 것입니다.
예
digits =[4,3,2,1]
[4,3,2,2]
설명 :
주어진 예에서와 같이 배열은 4321을 나타내고 4321 + 1은 4322가됩니다. 따라서 4322를 반환했습니다.
Plus One Leetcode 솔루션에 대한 접근 방식
모든 사람의 마음에 떠오르는 첫 번째 아이디어는 주어진 배열을 숫자로 변환하고 더하기 연산을 수행 한 다음 결과를 배열 형식으로 반환하는 것입니다.
그러나이 아이디어는 어떤 데이터 유형에도 맞지 않기 때문에 큰 크기의 배열에서는 실패합니다.
그래서 우리는 각 숫자를 하나씩 처리해야합니다.
- LSB에서 시작한 다음 MSB까지 각 숫자를 처리합니다.
- 현재 숫자가 9보다 작 으면 현재 숫자에 XNUMX을 더하고 배열을 반환하고 그렇지 않으면 현재 숫자에 XNUMX을 할당합니다.
- 마지막 요소가 처리되고 9와 같으면 모든 숫자가 9임을 의미합니다. 따라서 배열의 크기를 1 씩 늘리고 MSB에 XNUMX을 할당합니다.
- 배열 반환
실시
Plus One 용 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
vector<int> plusOne(vector<int>& digits) {
int n=digits.size();
for(int i=n-1;i>=0;i--)
{
if(digits[i]<9)
{digits[i]++ ; return digits;}
else
digits[i]=0;
}
vector<int>newnumber(n+1,0);
newnumber[0]=1;
return newnumber;
}
int main()
{
vector<int> arr = {4,3,2,1};
vector<int>ans= plusOne(arr);
for(int i=0;i<arr.size();i++)
cout<<ans[i]<<" ";
cout<<endl;
return 0;
}
[4,3,2,2]
Plus One 용 Java 코드
import java.util.Arrays;
public class Tutorialcup {
public static int[] plusOne(int[] digits) {
int n = digits.length;
for(int i=n-1; i>=0; i--) {
if(digits[i] < 9) {
digits[i]++; return digits;
}
digits[i] = 0;
}
int[] newNumber = new int [n+1];
newNumber[0] = 1;
return newNumber;
}
public static void main(String[] args) {
int [] arr = {4,3,2,1};
int[]ans=plusOne(arr);
System.out.println(Arrays.toString(ans));
}
}
[4,3,2,2]
Plus One Leetcode 솔루션의 복잡성 분석
시간 복잡성
위 코드의 시간 복잡성은 O (N) 숫자 배열을 한 번만 탐색하기 때문입니다. 여기서 n은 숫자 배열의 길이입니다.
공간 복잡성
위 코드의 공간 복잡성은 다음과 같습니다. O (1) 배열에 9보다 작은 숫자가 하나 이상 포함 된 경우, 그렇지 않으면 O (N).
