leetcode刷题笔记

11 妙用数据结构

11.2 数组

• 448 找到所有数组中消失的数字

// 方法1
// 1.使用一个数组的下标记录每个对应数字出现的次数
// 2.遍历数组，根据值为0的元素所在的下标确定没有出现过的数字
std::vector<int> findDisappearedNumbers(std::vector<int> &nums) {
    std::vector<int> count(nums.size());
    std::vector<int> result;
    for (int i = 0; i < nums.size(); ++i) {
        count[nums[i] - 1]++;
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (count[i] == 0) {
            result.push_back(i + 1);
        }
    }
    return result;
}

//方法2
//直接对原数组进行标记：将下标为(出现的数字-1)的元素的值设为负数，最后值为正数的元素所在下标+1即为没有出现过的数字
std::vector<int> findDisappearedNumbers(std::vector<int> &nums) {
    std::vector<int> result;
    for (int i = 0; i < nums.size(); ++i) {
        int position = std::abs(nums[i]) - 1;
        if (nums[position] > 0) {
            nums[position] = -nums[position];
        }
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] > 0) {
            result.push_back(i + 1);
        }
    }
    return result;
}

• 48 旋转图像

// 方法1
//(i,j)位置的元素旋转90°后变成了(j,n-1-i)位置(n为二维数组大小)
void rotate(vector<vector<int>> &matrix) {
    auto matrix_new = matrix;
    int n = matrix.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            matrix_new[j][n - 1 - i] = matrix[i][j];
        }
    }
    matrix = matrix_new;
}

// 方法2
// 每4个元素为一组：matrix[i][j] => matrix[j][n-1-i] => matrix[n-1-i][n-1-j] => matrix[n-1-j][i]
// 如何确定遍历的范围：如果n为偶数，则需要遍历n^2/4=(n/2)*(n/2)个元素；如果n为奇数，则需要遍历(n^2-1)/4=(n-1)/2*(n+1)/2个元素
void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int temp;
    for (int i = 0; i < n / 2; ++i) {
        for (int j = 0; j < (n + 1) / 2; ++j) {
            temp = matrix[n - 1 - j][i];
            matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
            matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
            matrix[j][n - 1 - i] = matrix[i][j];
            matrix[i][j] = temp;
        }
    }
}