寻找未排序数组中第N小的数字,使用Scanner。

huangapple 未分类评论58阅读模式
英文:

Finding the Nth smallest number in an unsorted array using Scanner

问题

我已经搜索了论坛,找不到如何在与扫描仪结合使用的情况下找到数组中第N小的数字的示例,所以如果这个问题之前已经在这里回答过,我很抱歉。此外,有没有办法显示程序查找数组中元素所进行的比较次数?如果可能的话,我已经附上了作业说明的图像。

public static void main(String[] args) {
    System.out.println("IDS201 HW3:\n");
    System.out.println("1. 生成 " + RANDOM_NUMBER_COUNT + " 个随机整数未排序的列表。\n");
    int[] randomNumbers = generateRandomNumbers();
    System.out.print("\n2. 查找值? ");
    Scanner stdin = new Scanner(System.in);
    int x = stdin.nextInt();
    int count = search(randomNumbers, x);
    if (count == 0) {
        System.out.println(x + " 不在列表中");
    }

    System.out.println("\n3. 对列表进行排序:");
    sort(randomNumbers);
    System.out.print("现在排序后的数组是:\n\n");
    display(randomNumbers);
} 

private static final int RANDOM_NUMBER_COUNT = 50;

private static void display(int[] randomNumbers) {
    int count = 0;
    for (int i = 0; i < RANDOM_NUMBER_COUNT; i++) {
        System.out.print(randomNumbers[i] + ",");
        count++;
        if (count == 10) {
            System.out.println();
            count = 0;
        }
    }
}

private static int[] generateRandomNumbers() {
    int[] randomNumbers = new int[RANDOM_NUMBER_COUNT];
    for (int index = 0; index < RANDOM_NUMBER_COUNT; index++) {
        randomNumbers[index] = (int) (Math.random() * 100);
    }
    display(randomNumbers);
    return randomNumbers;
}

private static int search(int[] randomNumbers, int x) {
    int i;
    int count = 0;
    for (i = 0; i < randomNumbers.length; i++) {
        if (randomNumbers[i] == x) {
            System.out.println("\n在数组中找到 " + x + " [" + i + "]");
            count++;
        }
    }
    return count;
}

private static int[] sort(int[] randomNumbers) {
    int size = randomNumbers.length;
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (randomNumbers[i] > randomNumbers[j]) {
                int temp = randomNumbers[i];
                randomNumbers[i] = randomNumbers[j];
                randomNumbers[j] = temp;
            }
        }
    }
    return randomNumbers;
}

[assignment instructions][1]
[1]: https://i.stack.imgur.com/X7PDw.png


请注意,我只翻译了您提供的代码部分。如果您需要更多帮助或有其他问题,请随时提问。

<details>
<summary>英文:</summary>

I&#39;ve scoured the forums and can&#39;t find an example of how to find the Nth smallest number in an array in combination with scannner, so I&#39;m sorry if this has been answered here before. Also, is there any way to display the number of comparisons that was made by the program to find an element within the array? I&#39;ve attached an image of the assignment instructions if it will help. [assignment instructions][1]

    public static void main(String[] args) {
	        System.out.println(&quot;IDS201 HW3:\n&quot;);
	        System.out.println(&quot;1. Generate &quot; + RANDOM_NUMBER_COUNT + &quot; random integer unsorted list.\n&quot;);
	        int[] randomNumbers = generateRandomNUmbers();
	        System.out.print(&quot;\n2. Search value? &quot;);
	        Scanner stdin = new Scanner(System.in);
	        int x = stdin.nextInt();
	        int count = search(randomNumbers, x);
	        if (count == 0) {
	            System.out.println(x + &quot; is not in the list&quot;);
	        }
	        
	        System.out.println(&quot;\n3. Sort the list:&quot;);
	        sort(randomNumbers);
	        System.out.print(&quot;Now the Array after Sorting is :\n\n&quot;);
	        display(randomNumbers);
	    } 
	 
    private static final int  RANDOM_NUMBER_COUNT = 50;

    private static void display(int[] randomNumbers) {
        int count = 0;
        for (int i = 0; i &lt; RANDOM_NUMBER_COUNT; i++) {
            System.out.print(randomNumbers[i] + &quot;,&quot;);
            count++;
            if (count == 10) {
                System.out.println();
                count = 0;
            }
        }
    }

    private static int[] generateRandomNUmbers() {
        int[] randomNumbers = new int[RANDOM_NUMBER_COUNT];
        for (int index = 0; index &lt; RANDOM_NUMBER_COUNT; index++) {
            randomNumbers[index] = (int) (Math.random() * 100);
        }
        display(randomNumbers);
        return randomNumbers;
    }

    private static int search(int[] randomNumbers, int x) {
        int i;
        int count = 0;
        for (i = 0; i &lt; randomNumbers.length; i++) {
            if (randomNumbers[i] == x) {
                System.out.println(&quot;\nFound &quot; + x + &quot; in array [&quot; + i + &quot;]&quot;);
                count++;
            }
        }
        return count;
    }

    private static int[] sort(int[] randomNumbers) {
        int size = randomNumbers.length;
        for (int i = 0; i &lt; size; i++) {
            for (int j = i + 1; j &lt; size; j++) {
                if (randomNumbers[i] &gt; randomNumbers[j]) {
                    int temp = randomNumbers[i];
                    randomNumbers[i] = randomNumbers[j];
                    randomNumbers[j] = temp;
                }
            }
        }
        return randomNumbers;
    }
}


  [1]: https://i.stack.imgur.com/X7PDw.png

</details>


# 答案1
**得分**: 0

你可以在[这里][1]找到用于在O(n)时间内找到第k小元素的顺序统计算法。对于扫描器部分,除了从命令行读取k并将其传递给算法之外,你不需要任何其他东西。与原始算法没有什么真正不同,两者都需要一个参数k,在这种情况下,你从命令行读取参数k。

**注意:** 还有其他解决第k小元素问题的方法,但它们较慢。例如,你可以对数组进行排序,然后从最后一个索引处找到第k个元素。你还可以在给定链接上找到其他方法的信息。

  [1]: https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/?ref=rp

<details>
<summary>英文:</summary>

You can find the order statistics algorithm to find the k-th smallest element in O(n) time [here][1]. For the Scanner part, you don&#39;t need anything other than reading k from the command line and passing it into the algorithm. Nothing really different from the original algorithm, both takes a parameter k and in this case, you read the parameter k from the command line.

**Note:** There are other approaches to the k-th smallest element problem, but they are slower. For example, you can sort your array and then find the k-th element from the last index. You can also find other approaches from previous entries on the given link.


  [1]: https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/?ref=rp

</details>



# 答案2
**得分**: 0

```java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        System.out.println("IDS201 HW3:\n");
        System.out.println("1. 生成 " + RANDOM_NUMBER_COUNT + " 个随机整数的未排序列表。\n");
        int[] randomNumbers = generateRandomNumbers();
        System.out.print("\n2. 要搜索的值? ");
        Scanner stdin = new Scanner(System.in);
        int x = stdin.nextInt();
        int count = search(randomNumbers, x);
        if (count == 0) {
            System.out.println(x + " 不在列表中");
        } else {
            System.out.println("比较了 " + count + " 次来进行搜索");
        }
        System.out.print("\n2. 第N小的值? ");
        int nth_value = stdin.nextInt();
        System.out.print("第 " + nth_value + " 小的元素是 " +
                nth_search(randomNumbers, 0, RANDOM_NUMBER_COUNT - 1, nth_value));
        System.out.println("\n3. 对列表进行排序:");
        sort(randomNumbers);
        System.out.print("现在排序后的数组是:\n\n");
        display(randomNumbers);
    }

    private static final int RANDOM_NUMBER_COUNT = 50;

    private static int partition(int[] randomNumbers, int l, int r) {
        int x = randomNumbers[r], i = l;
        for (int j = l; j <= r - 1; j++) {
            if (randomNumbers[j] <= x) {
                int temp = randomNumbers[i];
                randomNumbers[i] = randomNumbers[j];
                randomNumbers[j] = temp;
                i++;
            }
        }
        int temp = randomNumbers[i];
        randomNumbers[i] = randomNumbers[r];
        randomNumbers[r] = temp;
        return i;
    }

    private static void display(int[] randomNumbers) {
        int count = 0;
        for (int i = 0; i < RANDOM_NUMBER_COUNT; i++) {
            System.out.print(randomNumbers[i] + ",");
            count++;
            if (count == 10) {
                System.out.println();
                count = 0;
            }
        }
    }

    private static int[] generateRandomNumbers() {
        int[] randomNumbers = new int[RANDOM_NUMBER_COUNT];
        for (int index = 0; index < RANDOM_NUMBER_COUNT; index++) {
            randomNumbers[index] = (int) (Math.random() * 100);
        }
        display(randomNumbers);
        return randomNumbers;
    }

    private static int search(int[] randomNumbers, int x) {
        int i;
        int count = 0;
        for (i = 0; i < randomNumbers.length; i++) {
            if (randomNumbers[i] == x) {
                System.out.println("\n在数组中找到 " + x + ",位置为 [" + i + "]");
                count++;
            }
        }
        return count;
    }

    private static int nth_search(int[] randomNumbers, int l, int r, int k) {
        if (k > 0 && k <= r - l + 1) {
            int pos = partition(randomNumbers, l, r);
            if (pos - l == k - 1)
                return randomNumbers[pos];
            if (pos - l > k - 1)
                return nth_search(randomNumbers, l, pos - 1, k);
            return nth_search(randomNumbers, pos + 1, r, k - pos + l - 1);
        }
        return -1;
    }

    private static void sort(int[] randomNumbers) {
        int size = randomNumbers.length;
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (randomNumbers[i] > randomNumbers[j]) {
                    int temp = randomNumbers[i];
                    randomNumbers[i] = randomNumbers[j];
                    randomNumbers[j] = temp;
                }
            }
        }
    }
}

第N小的值函数

private static int nth_search(int[] randomNumbers, int l, int r, int k) {
    if (k > 0 && k <= r - l + 1) {
        int pos = partition(randomNumbers, l, r);
        if (pos - l == k - 1)
            return randomNumbers[pos];
        if (pos - l > k - 1)
            return nth_search(randomNumbers, l, pos - 1, k);
        return nth_search(randomNumbers, pos + 1, r, k - pos + l - 1);
    }
    return -1;
}

第2个函数

private static int partition(int[] randomNumbers, int l, int r) {
    int x = randomNumbers[r], i = l;
    for (int j = l; j <= r - 1; j++) {
        if (randomNumbers[j] <= x) {
            int temp = randomNumbers[i];
            randomNumbers[i] = randomNumbers[j];
            randomNumbers[j] = temp;
            i++;
        }
    }
    int temp = randomNumbers[i];
    randomNumbers[i] = randomNumbers[r];
    randomNumbers[r] = temp;
    return i;
}
英文:

here you go:

import java.util.Scanner;
public class Main
{
  public static void main (String[]args)
  {
    System.out.println (&quot;IDS201 HW3:\n&quot;);
    System.out.println (&quot;1. Generate &quot; + RANDOM_NUMBER_COUNT +
			&quot; random integer unsorted list.\n&quot;);
    int[] randomNumbers = generateRandomNUmbers ();
      System.out.print (&quot;\n2. Search value? &quot;);
    Scanner stdin = new Scanner (System.in);
    int x = stdin.nextInt ();
    int count = search (randomNumbers, x);
    if (count == 0)
      {
	System.out.println (x + &quot; is not in the list&quot;);
      }
    else
      {
	System.out.println (&quot;compared &quot; + count + &quot; times to search&quot;);
      }
    System.out.print (&quot;\n2. Nth Smallest value? &quot;);
    int nth_value = stdin.nextInt ();
    System.out.print (&quot;K&#39;th smallest element is &quot; +
		      nth_search (randomNumbers, 0, RANDOM_NUMBER_COUNT-1,nth_value));
    System.out.println (&quot;\n3. Sort the list:&quot;);
    sort (randomNumbers);
    System.out.print (&quot;Now the Array after Sorting is :\n\n&quot;);
    display (randomNumbers);
  }

  private static final int RANDOM_NUMBER_COUNT = 50;

  private static int partition (int[]randomNumbers, int l, int r)
  {
    int x = randomNumbers[r], i = l;
    for (int j = l; j &lt;= r - 1; j++)
      {
	if (randomNumbers[j] &lt;= x)
	  {
	    int temp = randomNumbers[i];
	    randomNumbers[i] = randomNumbers[j];
	    randomNumbers[j] = temp;
	    i++;
	  }
      }
    int temp = randomNumbers[i];
    randomNumbers[i] = randomNumbers[r];
    randomNumbers[r] = temp;
    return i;
  }


  private static void display (int[]randomNumbers)
  {
    int count = 0;
    for (int i = 0; i &lt; RANDOM_NUMBER_COUNT; i++)
      {
	System.out.print (randomNumbers[i] + &quot;,&quot;);
	count++;
	if (count == 10)
	  {
	    System.out.println ();
	    count = 0;
	  }
      }
  }

  private static int[] generateRandomNUmbers ()
  {
    int[] randomNumbers = new int[RANDOM_NUMBER_COUNT];
    for (int index = 0; index &lt; RANDOM_NUMBER_COUNT; index++)
      {
	randomNumbers[index] = (int) (Math.random () * 100);
      }
    display (randomNumbers);
    return randomNumbers;
  }

  private static int search (int[]randomNumbers, int x)
  {
    int i;
    int count = 0;
    for (i = 0; i &lt; randomNumbers.length; i++)
      {
	if (randomNumbers[i] == x)
	  {
	    System.out.println (&quot;\nFound &quot; + x + &quot; in array [&quot; + i + &quot;]&quot;);
	    count++;
	  }
      }
    return count;
  }

  private static int nth_search (int[]randomNumbers, int l, int r, int k)
  {
    if (k &gt; 0 &amp;&amp; k &lt;= r - l +1)
      {
	int pos = partition (randomNumbers, l, r);
	if (pos - l == k - 1)
	  return randomNumbers[pos];
	if (pos - l &gt; k - 1)
	  return nth_search (randomNumbers, l, pos - 1, k);
	return nth_search (randomNumbers, pos + 1, r, k - pos + l - 1);
      }
    return -1;
  }

  private static int[] sort (int[]randomNumbers)
  {
    int size = randomNumbers.length;
    for (int i = 0; i &lt; size; i++)
      {
	for (int j = i + 1; j &lt; size; j++)
	  {
	    if (randomNumbers[i] &gt; randomNumbers[j])
	      {
		int temp = randomNumbers[i];
		randomNumbers[i] = randomNumbers[j];
		randomNumbers[j] = temp;
	      }
	  }
      }
    return randomNumbers;
  }
}

nth smallest term function

private static int nth_search (int[]randomNumbers, int l, int r, int k)
  {
    if (k &gt; 0 &amp;&amp; k &lt;= r - l +1)
      {
	int pos = partition (randomNumbers, l, r);
	if (pos - l == k - 1)
	  return randomNumbers[pos];
	if (pos - l &gt; k - 1)
	  return nth_search (randomNumbers, l, pos - 1, k);
	return nth_search (randomNumbers, pos + 1, r, k - pos + l - 1);
      }
    return -1;
  }

and 2nd function

private static int partition (int[]randomNumbers, int l, int r)
  {
    int x = randomNumbers[r], i = l;
    for (int j = l; j &lt;= r - 1; j++)
      {
	if (randomNumbers[j] &lt;= x)
	  {
	    int temp = randomNumbers[i];
	    randomNumbers[i] = randomNumbers[j];
	    randomNumbers[j] = temp;
	    i++;
	  }
      }
    int temp = randomNumbers[i];
    randomNumbers[i] = randomNumbers[r];
    randomNumbers[r] = temp;
    return i;
  }

huangapple
  • 本文由 发表于 2020年7月28日 22:42:16
  • 转载请务必保留本文链接:https://java.coder-hub.com/63136773.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定