亚马逊经典面试题实例详解

前言

亚马逊是全球领先的电子商务和云计算公司，它在招聘过程中常常采用经典的面试题来评估候选人的技术能力和解决问题的能力。本文将详细介绍一个亚马逊经典面试题，并给出解决方案。

问题描述

假设有一个长度为n的整型数组arr，现在需要对数组进行排序，要求将所有负数放在非负数之前，且负数和非负数之间的相对位置不变。

解决方案

为了解决这个问题，可以使用双指针法来实现。具体步骤如下：

1. 声明两个指针，一个指针left从数组的第一个元素开始，一个指针right从数组的最后一个元素开始。

int left = 0;
int right = arr.length - 1;

2. 循环遍历数组，直到left指针和right指针相遇。

while (left <= right) {
  // 寻找第一个非负数的位置
  while (left <= right && arr[left] < 0) {
    left++;
  }
  
  // 寻找第一个负数的位置
  while (left <= right && arr[right] >= 0) {
    right--;
  }
  
  // 若left指针和right指针未相遇，则交换两个数的位置
  if (left <= right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++;
    right--;
  }
}

3. 循环结束后，数组中的负数都在非负数之前，且负数和非负数之间的相对位置不变。

总结

通过使用双指针法，我们可以高效地将一个整型数组中的负数放在非负数之前，并保持它们之间的相对位置不变。这种解决方案的时间复杂度为O(n)，其中n为数组的长度。在亚马逊的面试中，这样的问题可以展示出面试者对数组操作和算法的理解和实现能力。