在数组的线性搜索中查找相同值的多次出现

Question

如果该值在一个数组中出现不止一次，我该如何做到这一点，然后代码可以说该值出现在索引中：0、1 等？

我正在做一个家庭作业，它要求编写一个名为 linearSearch 的方法，该方法对整数数组执行线性搜索：搜索从索引 0 开始，然后是 1、2、3…。它应该 return 包含目标的数组的索引，如果在数组中找不到则为 -1。我已经这样做了，但我看到的一个问题是，如果目标在数组中出现不止一次，打印语句将只打印它最先出现的位置。例如，如果我的数组是 [6, 3, 9, 2, 7, 6]。打印语句说“6 is found at index: 0”。当该值出现不止一次时，有没有办法改变它，这样打印语句就会说“6 is found at index: 0 and 5”？

import java.util.Arrays;
import java.util.Random;

public class Q6 {
    public static void main(String[] args) {
        Random random = new Random();
        int x = random.nextInt(10);
        int[] y = createRandomIntArray(x);
        int z = x;
        System.out.println(Arrays.toString(y));
        System.out.println(z + " is found at index: " + linearSearch(y, z));
    }

    public static int[] createRandomIntArray(int n) {
        Random random = new Random();
        int[] result = new int[n];

        for (int i = 0; i < result.length; i++)
            result[i] = random.nextInt(10);
        return result;
    }

    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i;
            }
        }
        return -1;
    }

}
Output:
[6, 3, 9, 2, 7, 6]
6 is found at index: 0

Answer 1

我会用一个列表来存储找到目标数字的每个索引，然后在返回它们之前将它们全部添加到一个字符串中：

public static String linearSearch(int[] array, int target) {
    List<Integer> indices = new ArrayList<Integer>();
    for (int i = 0; i < array.length; i++) {
        if (array[i] == target) {
            indices.add(i);
        }
    }

    return indices.stream().map(String::valueOf).collect(Collectors.joining(" and "));
}

但我想您的教授还不希望您使用列表，更不用说流了。因此，这是另一种方法，它创建一个新数组来存储索引，使其与源数组大小相同，并使用变量 matches 来跟踪该数组中存储了多少索引：

public static String linearSearch(int[] array, int target) {
    int[] indices = new int[array.length];

    int matches = 0;
    for (int i = 0; i < array.length; i++) {
        if (array[i] == target) {
            indices[matches++] = i;
        }
    }

    if (matches == 1) {
        return String.valueOf(indices[0]);
    } else {
        String builder = String.valueOf(indices[0]);

        for (int i = 1; i < matches; i++) {
            builder += " and " + indices[i];
        }

        return builder;
    }
}

Answer 2

与其修改 linearSearch 方法的 return 值来处理多个匹配项，不如添加搜索的起始位置。

public static int linearSearch(int[] array, int target, int off) {
  for (int i = off; i < array.length; i++) {
      if (array[i] == target) {
          return i;
      }
  }
  return -1;
}

然后您将（可能）进行多次调用，使用先前识别的匹配项的位置作为下一次搜索的起点。当你找不到匹配时你就退出了。

public static void main(String[] args)
{
    int x = 6;
    int[] y = {6, 3, 9, 2, 7, 6};
    
    int off = 0;
    while(true)
    {
        off = linearSearch(y, x, off);
        if(off < 0) break;
        System.out.println("Found at index: " + off);
        off += 1;
    }
}

输出：

Found at index: 0
Found at index: 5

在数组的线性搜索中查找相同值的多次出现

Finding multiple occcurances of the same value within a linear search on an array

java

eclipse

arrays