2023华为OD机试真题【计算数组中心位置】【Java Python C++】

川长思鸟来 2023-09-27 17:35 38阅读 0赞

### 题目描述 ###

给你一个整数数组nums，请计算数组的中心位置。数组的中心位置是数组的一个下标， 其左侧所有元素相乘的积等于右侧所有元素相乘的积。数组第一个元素的左侧积为1，最后一个元素的右侧积为1。 如果数组有多个中心位置，应该返回最靠近左边的那一个，如果数组不存在中心位置，返回-1。

**输入**

2 5 3 6 5 6

**输出**

### 题意解读 ###

左侧积：该元素左侧所有元素的乘积；  
右侧积：该元素右侧所有元素的乘积；

例如**元素3**，他的左侧积是 `2*5 = 10`. 他的右侧积是`6*5*6 = 180`  
![在这里插入图片描述][d9cbfdaacffc4de8896b397815f98b43.png]

**数组的中心位置指的是**：该元素的 `左侧积 等于 右侧积`

### 解题思路 ###

遍历整个数组，在遍历的过程中，计算当前元素**左侧所有元素的乘积**（`leftProduct` ）和右**侧所有元素乘积**（`rightProduct` ），当`leftProduct == rightProduct`，表示找到了中心位置。

那么，如何初始化左侧积`leftProduct` 和右侧积 `rightProduct` 呢？`leftProduct` 初始值为 1，`rightProduct`初始值是**所有元素**相乘。

初始化完成后，开始遍历数组，从左到右的顺序遍历 。对于当前位置 i，首先更新左侧积（如果 i 不是第一个元素，那么左侧积为 `leftProduct * nums[i-1]`），然后更新右侧积（`rightProduct / nums[i]`）。

如果左侧积和右侧积**相等**，则表示`i`就是中心点。

### 视频讲解 ###

2023华为机试真题【计算数组中心位置】

### 示例代码（Java版本） ###

import java.util.Scanner;
    
    public class Main {
        
    
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            String[] inputs = scanner.nextLine().split(" ");
            int[] numbers = new int[inputs.length];
            
            for (int i = 0; i < inputs.length; i++) {
        
                numbers[i] = Integer.parseInt(inputs[i]);
            }
    
            int index = findCenterIndex(numbers);
            System.out.println(index);
        }
    
        public static int findCenterIndex(int[] nums) {
        
            if (nums.length == 1) {
        
                return 0;
            }
    
            int n = nums.length;
            int[] leftProduct = new int[n];
            int[] rightProduct = new int[n];
    
            leftProduct[0] = 1;
            rightProduct[n - 1] = 1;
    
            for (int i = 1; i < n; i++) {
        
                leftProduct[i] = leftProduct[i - 1] * nums[i - 1];
            }
    
            for (int i = n - 2; i >= 0; i--) {
        
                rightProduct[i] = rightProduct[i + 1] * nums[i + 1];
            }
    
            for (int i = 0; i < n; i++) {
        
                if (leftProduct[i] == rightProduct[i]) {
        
                    return i;
                }
            }
    
            return -1;
        }
    }

### 示例代码（Python版本） ###

def find_center_index(nums):
        if len(nums) == 1:
            return 0
    
        n = len(nums)
        left_product = [1] * n
        right_product = [1] * n
    
        for i in range(1, n):
            left_product[i] = left_product[i - 1] * nums[i - 1]
    
        for i in range(n - 2, -1, -1):
            right_product[i] = right_product[i + 1] * nums[i + 1]
    
        for i in range(n):
            if left_product[i] == right_product[i]:
                return i
    
        return -1
    
    
    nums = [int(x) for x in input().split()]
    index = find_center_index(nums)
    print(index)

### 示例代码（C++） ###

#include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    int findCenterIndex(vector<int>& nums) {
        
        // 长度为1特殊情况
        if (nums.size() == 1) {
        
            return 0;
        }
    
        int n = nums.size();
    
        // 左侧和右侧的乘积
        vector<int> leftProduct(n, 1);
        vector<int> rightProduct(n, 1);
    
        // 计算每个位置的左侧乘积
        for (int i = 1; i < n; i++) {
        
            leftProduct[i] = leftProduct[i - 1] * nums[i - 1];
        }
    
        // 计算每个位置的右侧乘积
        for (int i = n - 2; i >= 0; i--) {
        
            rightProduct[i] = rightProduct[i + 1] * nums[i + 1];
        }
    
        // 比较左侧和右侧的乘积来找到中心索引
        for (int i = 0; i < n; i++) {
        
            if (leftProduct[i] == rightProduct[i]) {
        
                return i;
            }
        }
    
        // 如果没有找到中心索引，则返回-1
        return -1;
    }
    
    int main() {
        
        int n;
        vector<int> nums;
        while (cin >> n) {
        
            nums.push_back(n);
        }
        int index = findCenterIndex(nums);
        cout << index << endl;
    
        return 0;
    }

[d9cbfdaacffc4de8896b397815f98b43.png]: https://img-blog.csdnimg.cn/d9cbfdaacffc4de8896b397815f98b43.png