Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

First Missing Positive #64

Closed
Tracked by #100
fkdl0048 opened this issue Oct 8, 2024 · 0 comments
Closed
Tracked by #100

First Missing Positive #64

fkdl0048 opened this issue Oct 8, 2024 · 0 comments
Assignees
Labels
Milestone

Comments

@fkdl0048
Copy link
Owner

fkdl0048 commented Oct 8, 2024

// 1. 무식하게 풀기
// 배열을 순회하며 1부터 검사 = count
// 값이 있다면 count 증가
// 0이나 음수는 무시

// O(n)에 돌아야하기에 불가능
// 

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int count = 1;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < 0) continue;

            if (count == nums[i]) count++;
        }

        return count;
    }
};
  • 쉽게 풀이하는 방법은 다음과 같다. 하지만 시간 복잡도 때문에 인덱스를 숫자 그대로 정렬하는 기법이 필요함
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        // 배열을 정렬하는 대신, 각 숫자를 그 숫자가 있어야 할 위치로 이동
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

        // 첫 번째로 잘못된 위치의 숫자 찾기
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 모든 숫자가 제자리에 있을 경우, n + 1이 첫 번째 누락된 양수
        return n + 1;
    }
};
@fkdl0048 fkdl0048 mentioned this issue Oct 8, 2024
7 tasks
@fkdl0048 fkdl0048 self-assigned this Oct 8, 2024
@fkdl0048 fkdl0048 added this to Todo Oct 8, 2024
@github-project-automation github-project-automation bot moved this to Todo in Todo Oct 8, 2024
@fkdl0048 fkdl0048 closed this as completed Oct 8, 2024
@github-project-automation github-project-automation bot moved this from Todo to Done in Todo Oct 8, 2024
@fkdl0048 fkdl0048 added this to the LeetCode milestone Oct 8, 2024
@fkdl0048 fkdl0048 mentioned this issue Oct 15, 2024
47 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
Status: Done
Development

No branches or pull requests

1 participant